Exchange problems

I recently implemented an exchange 2000 server. Every one in my company converted nicely into their exchange mailbox except of course the VP of Operations! When I did get his mailbox created correctly, when new mail would enter his mailbox it would stay bold faced(not read) for ten or fifteen seconds and then automatically "un-bold" itself. I thought it might be a corrupt registry key somewhere on his local machine and that the issue was with MS Outlook. However I recently place a brand new machine in his office, connected him to the exchange server and got the same results. You wouldn't think this would be that much of an issue, but this guy is freaking out. To temporarily solve the problem I have disconnected him from the exchange serverand have set him up with a normal internet e-mail account. This is only going to work until I begin breaking out some of the bells and whistles that exchange posseses, ie. instant messaging, scheduling and so on. I have searched Microsoft's databasewith no success. I have even bought books on troubleshooting exchange with no luck. Do you guys have any ideas????