After you restart the BES, you get into the realm of SDR53831.
Here is RIM's description of that SDR:
"If the BlackBerry Messaging Agent is restarted and there are a large number of over-the-air folder management (OTAFM) commands in the WorkQueue table of the configuration database with a status of 0, users experience a delay, of up to a few hours, before receiving messages on the handheld."
That's from the SP1 release notes:
http://www.blackberry.com/knowledgec...46092&vernum=0
After you restart your server, you can look in the MAGT (Mailbox Agent) log and you will see that OTAFM packets are being successfully delivered to the handheld. Meanwhile, the pending count goes through the roof. Once all of these OTAFM items are processed, mailflow returns to normal.