This has been happening to me for a very long time and I finally figured it out! All the documentation online points to this being a space issue, and it is. But not like you would think!
The attached error message below shows the Event Log on our server. The events that were being logged were ID 3005, described as ActiveSync errors. Inside the events you could see that an HTTP 507 was occurring.
Since a user is stored in active directory, I checked the size limits there. No dice. The problem isn't in the SIZE of the mailbox, but rather in the number of items in folder. With active sync, the "suggested limits" from Microsoft are what are used as hard and fast limits.
See this article for the folder limits:
In my case, I am running Exchnage 2003 SBS R2. This means I have a "limit" of 5,000 items per folder.
In the example I had, I have a mailbox that is used ONLY as a calendar and is shared by all users of my organization. I had copied over all the appointments from my old server when I first set it up. This resulted in a ton of old appointments in the calendar. When I checked the NUMBER of items, I had over 6,000. This is why active sync was blocking the connection from the phones. Note that when I first setup the exchange server with this mailbox, I did not have this problem, because the total number of items was below 5,000. As soon as the calendar went over 5,000, all phones using activesync no longer worked and the event log started catching the errors.
TO FIX: I went into the folder in Outlook 2010 on my local PC (which by the way does not have any of these so called "limits"). I used the mailbox cleanup wizard under "File" to archive all items older than 5/1/2008. This moved out almost half of the items in the folder and got me back to under 5,000. As soon as this was done, activesync on my phone (an iPhone) started working again like it never left.
Note, there are no error messages on my phone when this condition occurs. I found them only in the event log on the server. This pointed me towards the final problem, which was the number of items rather than the size of the mailbox.
To see how many items are in a mailbox, you can use "Exchange System Manager" and drill down to the node for "Mailboxes". Since this mailbox had no folders being used other than the calendar, I was able to assume the total number was the correct total for the calendar.
Another way to do this would be to login to the mailbox using outlook and then do a list view on the calendar to get the total number of items.
Finally, you can right click on the calendar in Outlook 2010 and in the properties you can get a total item count.
Hope this helps someone else!!!