I am wondering if anyone is aware of a solution that would allow me to update/maintain a separate address book from the users own. We are trying to determine the best solution to get vital company contact information which tends to change frequently to a select group of users ideally via an OTA install/update. I am not so concerned that it is completely integrated with their pab on the device, but at least have some similar functionality that allows them to select a contact and either call/e-mail from the menu. Has anyone heard/seen such a thing?

No such animal, AFAIK. The closest solution would be some online account like GMail that can be accessed by anyone with the password.

Check out Upvise can be sync to multiple device and works independently with your address book. Its also free!