A device, system, and method are directed towards enabling a mobile device user to perform a federated search across a plurality of disparate contact data stores, including a phone directory, IM store, an email address book, a buddy list, a social networking group, a SMS list, or any of a variety of other communication contact data stores. When a user inputs a character, a dynamic search is performed across the various contact data stores. The results of the search may be repeatedly updated based on additional input characters. The results of the search may be displayed on the mobile device organized by categories of the contact data stores and/or a preferred communication mechanism. The results may also indicate a preferred mechanism for communicating with the displayed name.