Licensing , User Mailboxes and Reconcillation

The fact that it retains the data (the hold is still active) doesnt mean that the object is in the "correct" state, as it's now technically in violation of the license agreement. Microsoft made a deliberate decision not to remove any mailboxes put on hold even when no matching license is assigned in order to avoid data loss. This does not mean that you are free to use this functionality without effectively "paying" for it. Moreover, since this is not a *supported* scenario, they can change the behavior at any time. Stick to what the recommend/support.