After restarting your user it is normal to see pending messages.
Keep in the mind that after you restart the BES it is rescanning the Exchange mailboxes of every user on your server. If you have a lot of users or users that have large mailboxes it can take quite some time. Normally 10-25 minutes is not uncommon.
Check application and BES logs (MAGT log) for errors as well.
If your users are experiencing clumping (receiving emails in bunches) then there is another issue in your environment.
1) Check ping response time between BES and Exchange
2) Make sure there are no version mismatched between Exchange & BES (mapi32.dll, cdo.dll)