This is a problem with ActiveSync from a phone (Windows Mobile 6.5).
I've encountered this on two separate servers so far. The one I'm currently working on is Windows Server 2003 (32 bit) running Exchange 2003. At one time, it was the only Exchange server in the network and ActiveSync ran just fine. Then I added a Windows Server 2008 system running Exchange 2010 and was hitting that one for ActiveSync. That second server died and so I had to fall back to the original server (the Exchange 2003 one). OWA works fine. However, ActiveSync, which had been working fine on this system previously, now will only sync if the account it's directed at holds only a few items. When I set the phone to only sync the email, it will do that fine as long as there are only a few items in the inbox. When the inbox has more than a few items, or if I set the sync to include contacts or calendar, it will hang indefinitely on "Looking for changes."
Looking at similar problem reports, some resolutions have related to antivirus or backup software on the server. I was running Carbonite backup, but I did uninstall this with no change. For antivirus, I'm running MS Security Essentials. I turned off the active monitor mode on that, also with no success. I would note that both of these were in place when the server was running successfully before.
The server event log shows no errors and the phones do not give an error.