I recently had another instance where mobile phones (Android) refused to connect to an Exchange 2003 server. Using https://www.testexchangeconnectivity.com/, it stopped at

The help at Microsoft was misleading because I have already followed those steps. In this case, the issue was resolved by removing the Host Header Value from the Default Web Site in IIS:

Once that entry was removed and I restarted the IIS Admin service, ActiveSync started working again.

UPDATE 2011-09-15: I rebooted the server, and it again failed like this. In this case the host header value was still clear. The fix in this case was to run iisreset again. Not sure why, maybe because some services did not come up right and had to be hand started, and that caused some side effect with ActiveSync.