There is described an interconnect hub for routing an Instant Message (IM) or related communication between a sending IM device in a first IM community and a recipient IM device in one of a plurality of potential second IM communities. The interconnect hub comprises a router for determining the destination of IM communications and routing the IM communications to the intended recipient, a search function for finding the service provider providing IM services to the user identifier, and a cache comprising a plurality of records associating user identifiers with corresponding service providers (mobile or Internet). When the IM communication is received by the interconnect hub, the router examines the recipient user identifier, accesses the cache keying on the recipient user identifier, retrieves the service provider associated with the recipient user identifier, and forwards the IM communication to the associated service provider for delivery to the intended recipient. If there is no record in the cache for the user identifier, the searcher initiates a search to identify the service provider and to update the cache if the service provider is found.