We had the same mail arrangement that you described (we are also a small company), just not that long ago (just over a year and a half).
What we did (and in fact still do to an extent) is we instructed the users on how to update the address books. Our users were then responsible for updating their own address books. It worked surprisingly well.
Of course you'll get the occassional user who doesn't understand, but after you show them they'll get it eventually.
That all said, you don't mention what is your mail server you just say you down host your own email yet. Its the mail server that determines if the address information is "automatically" pushed to the clients or not.
Anyway, we now host our own email. We use Ipswitch's Imail Server 7.07. It works beautifully, our company is very pleased with it. And its a cinch to install and configure - very straightforward.
What's more, no expensive fees associated with Exchange Server!!! We have unlimited user license rights for about $3000 - so no worries!
www.ipswitch.com
good luck.