Did they back up his email at all before removal? If not, you may not be able to recover it unless your company has some sort of retention policy where they can recover deleted accounts.

I am assuming this is on an Exchange Server, correct?