Thanks @StephanG for the share so that others experiencing the same thing can more easily reference this!
By the way, since the Microsoft Q&A community has a policy that "The question author cannot accept their own answer. They can only accept answers by others", I'll repost your solution in case you'd like to "Accept" the answer : )
[Recycled user does not get mail - automatic re-attaching mailbox did not work]
Issue Symptom:
" some users got deleted by mistake in the cloud - after the next sync with AD connect the users was restored.
But the mailbox reattach process seems to have a problem with one user. First it was no available at all at the Exchange GUI. With Powershell i performed an undo-softdeletedmailbox - but got also errors on this.
Now 10h later i still cannot address the user from internal and external. "
Resolution:
The IsSoftDeletedByRemove
property value must be set to false to fix the problem. The property value "IsSoftDeletedByRemove" has been set to "false" with our diagnostics and thus the SoftDeletionCorruption error no longer exists. Therefore, I would like to ask you to check the behavior again and inform me about it.
After that we could address the user and after another night he appeared in the GAL and Teams.
Maybe related to the 8h OAB rebuilt schedule.