Can you leave and retrive voice mails over the phone for those users that don't see them in their inboxes? If so, sounds like seperate mailboxes were made for these folks' voice mail - accidentally or otherwise.
If you can't leave/retrieve messages then we'll want to run it down by figuring out where the messages ARE going for these folks. You'd want to look for any messages going to the Unaddressed Messages distribution list and for any errors in the application event log...
