Is OMA working?

from your post, I assume you use SSL, not form-based authentication. Did you check that the certificate is trusted and properly installed?

I don't use exchange 2003/2007, but Apple and MS have some detailed instructions on how to setup the exchange/mobile device. Check them first.