Try this, Go into your Messages> Messages Options> Email Reconciliation> and check your "Wireless Reconcile" (that should be set to "yes").
If that is set to yes already, you can try Regenerating Encryption Keys:
From the main menu, access your Settings> Options> Security Options> General Settings> highlight "Desktop" (right under Services
> and press your trackwheel in, and select "Regenerate Encryption Keys."
Then once that's completed, perform a battery reset.
If THAT fails, try plugging your Blackberry into your PC and run the Blackberry Desktop Manager Software and do a wired-sync.