While this doesn't directly address the issue of access to older Exchange mail on the Blackberry, it does provide a facility for those who would like full access to their historical email store. It's not that hard, it makes some assumptions, and it might even work

Look into Google Apps for Domains and the Google Mail Uploader. If you're on OL with a local (.pst) email store, you can simply upload all of your email to a GAFD email account, install the GMail client on your BB, and everything you've ever sent and received through that account is now fully searchable, retrievable, and organized by folder (using labels).

If you're on a hosted (vs Corporate) Exchange server using BES, archive all of your hosted mail to a local .pst, upload that to GAFD, and forward your hosted mail to GAFD. Then cancel your hosted account

The only significant drawback to the Gmail client is that it uses your Google address book rather than the BB's. You can sync your BB address book to Google by first syncing it with Outlook, exporting it to .csv, then uploading it through the GAFD web interface; Google did a great job of parsing the file and populating its address book from it. Unfortunately, it's not a fully automatic "sync" process, although I suspect that will change soon.