On my new Pearl, one of my email accounts setup via BIS didn't work after a couple of messages. The VZ rep sent me new service books, didn't work. So she connected me to a BlackBerry tech and he walked me through on cleaning out the email database. A delete prior on the very top does this. He also added, if that didn't work, was to use the Desktop Manager's Backup and Restore Utility to delete the items in the particular account.
So there are three tiers to this issue:
1-New service books sent to your BB device. (rare to get to this point)
2-Delete prior on the very top (even rarer, since new service books take care of the issue)
3-Desktop Manager to completely clean items out, including corrupted ones that eek past the delete via the handheld.
So if the Service Books are no dice, call your carrier and ask to speak with their technical support. They will walk you through this, or connect you to BB.
I have to say, my call to BlackBerry was a reminder on how great their tech dept is. We called them all the time with the weirdest issues at my previous company, and they were all very knowledgeable and friendly.