I did this a few months back for a user and it was a total stuff around but I got it working. I have to again but I have forgotten something.
Can log into OMA via web so its definetly something on the Iphone itself.
New mail account -> Exchange
domain: NETBIOS DOMAIN name
Use SSL: No
I have tried with username: DOMAIN\username too, before I had to turn off SSl as we don't use it. not sure if I need the /OMA on the end ?
Any ideas before the Iphone gets smashed to pieces :-)