Let’s get a bit more specific here–is it Exchange 2003 or 2007 we are talking about? It will not make much difference, except in the location of some files we will be looking at. What is the SMTP error code you are receiving? Have you looked at the SMTP logs to see what they can tell us about the attempted delivery?
The last time I had a similar situation, I needed to reinstall Exchange (worst case scenario, but prepare for it), but we may be able to work around this without doing anything so drastic.