Exchange doesn’t normally delete the mailbox straight away. Have you checked in System Manager in the mailbox store to see if it’s still there; disconnected with a red cross next to it? If you got lucky you need to create a new user without a mailbox then you can attach this deleted mailbox back to this new user. Otherwise, sorry if no backup or pst I can’t think of a way to recover it.
Maybe there is an archive pst? What about offline folders? (.ost I think.)