Searching a contact address book/directory of users & non-users

I'm currently scouting for a suitable solution for a new site i'm putting together. It's probably something quite common on Intranet style sites rather than blogs or general public websites.

The staff of the company each have a drupal profile with some additional details in - telephone number, company name (all the same), department etc.

I then want the users/staff to be able to add their contacts/clients/suppliers, which can be shared within the company. It would become a business card repository.

I've checked out a few options in Drupal as it stands, but am wondering if there are more or alternative solutions.

Contact_dir.module allows each drupal user to build up a (slightly)searchable address book of contacts which can be shared. The idea here is okay, and the fields in the address book are configurable with some source code hacking. However the search is poor and only works on a persons name, rather than company name.

Profile.module/members.module has a great system for drilling down searches. It's intuitive for users to click on a country name and get all contacts in that country, or all contacts within a department. However it falls over because it relies on each contact also being a drupal user. How can non-site users/members be added to the searchable list?

Flexinode could be used to create a node with the right contact detail fields. These would then be searchable using the standard Drupal search engine. However the great profile.module search system would not be available then.

It would also be great to get a simple A-Z listing of all contacts too, should people wish to browse rather than type in a name to search.

i think i'm after a bit of a few modules here, but maybe there is something else lurking out there? Maybe in CVS that I do not know of. Can anybody help suggest a suitable solution to my problem?

Thanks.