I have the exact same problem as described, with Exchange 2003. BES version 126.96.36.199. Also around 50 users. It's driving me crazy. I will look into the MAGT log. Please post back if anyone figures anything out.
The only common thread we can find is it seems to only happen with Blackberry 9630's. But that could be a coincidence as there are two people that this happens to every couple weeks with them. I have only seen it happen to about 4 people all told, all with 9630's. But we have a lot of those phones.
Oh also, when this happens they can send emails, just not receive. I'm hoping we have the same issue and I'm not thread jacking here