A method and system is described for facilitating instant messaging (IM) between a first user with an address that includes a first domain name and a second user with an address that includes a second domain name different from the first. A substitute address is chosen that includes the second domain name and is mapped to the first address. An IM sent from the first user to the second is copied and re-addressed to be sent from the substitute address. This maintains consistency of domain names between the addressor and addressee, allowing existing IM systems that inhibit IM between incompatible IMSPs to deliver the message.