Are you able to provide more details about the Exchange virutalzation (OS version, Exchange version, Was it installed fresh or was it a P2V conversion, are any other programs having email problems)? If it were me, I would start by having a look at the Exchange queues and watching them when you send various test messages. The goal would be to identify whether the test messages were making it into Exchange or were getting stopped before they got in.