I had a similiar problem and it took forever to find the fix, but i got it. What you need to do is this:
Open IIS manager
Go down to your SMTP Virtual Server | Properties |access tab
Go down and click the connection button
Ensure ALL EXCEPT THE LIST BELOW radio button is checked.
By default, the ONLY THE LIST BELOW is checked, and when i changed to the other one, mail started to flow like a river. Test is out after mail works by changing it back, you will see what I mean.
One more thing, make sure you restart the services on the SMTP Virtual Server after you make the change.
Cheers,
Ryan