My MD had a clear out of her mailbox (anything from september 2011 back to 2005 was deleted!) she is now majorly regretting this as there was contracts etc etc in there.
Now I have looked in OWA but the deleted items are all gone, what gives me a glimmer of home is that in exchange I am still seeing 40K items under her AD account not 2.5K.
Is there any way to get these messages back through Exchange as it is still showing all messages as stored?
If she hasn't purged the items in the "recover deleted items" folder, you can still get them back there. You can get to that by (in outlook 2003) right clicking the deleted items folder in her mailbox and selecting "Recover Deleted Items...". Although, I believe for this to work with Hard-Deleted items, you would have had to previously enabled Recover Deleted Items functionality for all folders (registry edit).
If she has cleared out the messages from the Recover Deleted Items folder, then you'll need to restore from a backup.