We have an Exchange 2003 SP2 server. ActiveSync was working fine for variety of mobile devices. It still works for existing devices. But if you add any new device, it can connect to the server but it won't sync. Same is true if you take an existing device (which is working), remove the account and set it up again. Then it fails to sync.
I have confirmed that ActiveSync is configured properly on https://testconnectivity.microsoft.com/
I do not see any specific errors in event logs. I would appreciate any help on this.