You should be able to export your mailbox to a pst file from within outlook (if the PC isn't connected to the exchange server it'll use the OST file which is the "Cache", and you should be able to export it still). There are 3rd party tools you can use for the same thing, and also to recover deleted mail, check out the Stellar Recovery programs for that.
If you are talking about recovering IMAP based mail, that is usually not possible, as the mail is on the server and not local.
I can't exactly follow the reason behind moving from exchange to imap. You loose groupware functionality that way (Calendars, Contacts, Tasks etc.).
