How do I restore the mailbox of a deleted user

Hello, I had someone delete a valid user last week, and then they recreated the user in a panic(same login etc etc)..... I am now given the task of restoring their mailbox....

It is proving quite a challenge..... I have their OST file, and in exchange I have their mailbox which is set to deleted state (with the little red x on the icon)

If I try and just reconnect the mailbox to a temp user (then extracting the data and importing to the new mailbox), it gives me the error:

This legacyExchangeDN value is already being used by '................'


Im not too sure if this is due to the fact that a new user with the exact same details has been setup?

I cant recover from the OST file, because the current username doesnt have access (something similar to the new username having a new ID)

and if I go for recovering from backup, I have to create a backup server as the user has been deleted....


I think my best shot is to maybe try and work with the deleted mailbox already located on the exch server... anyone know how I would get around that error? or any other way?



Thanks,
Nathan