There is a trick to this: I have switched since from an Outlook Exchange provider to an regular IMAP/POP3 email provider. As I did not need the old emails at that time, I've just saved the .ost file – you guessed – I need some of the old email.
I found some good pointers here, but I'm still investigating.
Best Answer
.ost is just a local cache, it's not meant for data retrieval, especially if your exchange account is removed from your machine or the account is deleted, so normally one would say "sorry" if you didn't export your mail to a .pst, backup file or similar and the exchange host does not have a backup copy for you.
There are tools that can recover items from it though it comes with no guarantee. I've used Recovery Toolbox for Outlook with some success for some unfortunate first-time clients. The last version I purchased had problems correctly saving to .pst file so the end result was a lot of flat files to import, but it worked for e-mails, contacts and calender items. I never did get any useful results of the free tools I tried first, though this was a year or two ago.