Hi
Do you see the de-attached mailbox in Exchange System Manager? At what stage does the re-attachment process fail?
If you are not seeing the de-attached mailbox, you might want to run the clean up agent which should force the process a little quicker.
You might also want to check the deleted mailbox retention period, ensure it is not set to zero or a low value.
Regards
Ben Hoffman
Microsoft MVP - Windows Server System Exchange