Company Wide Contacts in Exchange

I have a customer that would like to have two shared contacts folders (one for vendors and one for subcontractors) that are both viewable and editable organization wide. They are currently running W2k8 SBS with Exchange 2007. They also want these folders to be available on their mobile devices.

I know that is possible to create public folders to do this, but from what I've read Microsoft is fazing out the public folders feature. I believe the suggestion MS is making instead is to use Sharepoint for sharing contacts, but that solution will not allow them to sync them to mobile devices, and besides they have not begun using Sharepoint at all in this organization so it would introduce a large learning curve to overcome for the users.

I also considered creating OU's and putting all the contacts in AD. The issue with this is that  I would have to give users limited rights to AD and install the interface on all workstations and train the users on how to add contacts in AD... a lot of work as well as a learning curve for me as I have never setup user to have limited rights to AD. Also since this is SBS does MS count contacts in AD as users using CAL's and does it limit the amount of contacts in any way?

The only other solution that I can come up with is creating two additional full mailboxes and giving all users rights to those mailboxes. This should allow them to set them up as a second account on their mobile devices as well view them in Outlook. Seems like it should work except it feels like a band-aid solution to me and that there has to be a better way to accomplish this.

Any thoughts? ...actually now that I think about it... maybe if there is an affordable and simple CRM tool that integrates with Exchange and accomplishes the same things I can push them that way, since essentially I guess what they are doing is trying to use Outlook a little bit like a CRM.

Thanks in advance,
-Al