I have two iphones, both running version 4.0.2.
When setting up an exchange account with identical settings one connects and verifies fine and I can use email fine.
The other allows me to enter the email address, domain, username and password, whch it verifies without error. Upon entering the mail server information, it fails verification (account verification failure).
So I have deduced that the SBS 2003 server has been set up fine, and there must be some setting on the iphone causing the issue.
I have tried resetting the network settings, deselecting sync options with mail/calendars etc in Itunes.
The only difference between phones is that the owner did have a faulty phone, and this was a replacement and Itunes was used to populate the new iphone with backed up date from the old phone.