Scooby, if the suggestions here don't resolve your issue, I'd recommend you look at testing disabling anti-spam software that may be interacting with your Outlook/Exchange setup. We had a long thread here a while back, in which another forum member was able to trace a very similar issue on an Omnia II to a McAfee anti-spam toolbar installed in Outlook. This was despite the fac that the member was syncing with Exchange over the air - sounds crazy, but it seemed pretty clear that was the problem.
Here is the thread.