Here is some backstory before I get to the issues.
This client was on hosted exchange, we have installed a new SBS 2011 and imported their email via PSTs into exchange.
They have 4 users with iPhones, 2 of them work with no problem. The other 2 sync work briefly for a time when it stops working you can go to the mailbox and it spins saying checking for mail.
One user went a week before it stops working the other goes only 1 day before it stops.
I have done the following in an attempt to resolve:
Removed and re added the account
Removed mobile device partnership from exchange and readded to phones
One of the users completely replaced their hardware and the problem persists
Have tried using IP Address instead of server name on the phone settings.
I have reset both their passwords.
Restarted their router when the issue occurs and it does not resolve.
The server does not state their are any errors with their mailboxes or active sync. Both are iPhone 4 with iOS 5.1.