The behavior you are describing is very odd. The mailbox holds the hidden messages, not the Outlook client.
Make sure the users Outlook profile is not enabled for Cache Mode.
Run the ResetEVClient.exe on the effect user’s machine while logged on as that user.
ResetEVClient Utility
http://support.veritas.com/docs/293258
If you are positive that each Outlook client is connecting to the same mailbox you can look at the hidden messages and verify they are correct. You can even delete the hidden messages and then synchronize the mailbox which will push the hidden messages back. This does not sound like the cases though but may worth reviewing.
How to delete hidden messages from Outlook on the client in Enterprise Vault (tm) 7.0 and 2007.
http://support.veritas.com/docs/287572