We've had similar incidents at our office after our Blackberry server took a nose-dive! Unfortunately none of our users had backed up their device any time recently and the phones had to be wiped and re-added after we built another server.
Our administrator had added all of our Blackberry users to the new server and setup their account without an activation password. Sometime after he had done this, all Blackberry users were once again communicating but had none of their old messages.
We are running Exchange 2010 and store all messages on the server with, of course, mailbox quotas. The question became to me "why would you want to save all of that old stuff on your Blackberry when the server already has a copy?"
Our instructions to our users was simply this, if you know the sender's name, subject or any other pertinent information, why not simply perform a "remote mailbox search."
To do this, as an example, from within your mailbox click on the menu buttion; select search; scroll over to the magnifying glass and select it and scroll down to "advanced search." From here, you can enter such things as where to search (device or remotely), the name, the subject and even the specific mailbox where you may have filed the message.
You'd think people would not like this change but, low and behold, they actually find it easier than scrolling down through the corucopia of messages they may have in their mailbox.
We hope this is of use to some of us dedicated Crackberry users!