After a night of debugging we found the answer: It was the smart card removal policy that created the issue. We first ruled it out because the disconnects even happened on clients without smart cards but in the end, the smart card service was the culprit. Which in hindsight makes perfect sense, it is a service that lives in session "0" and is disconnecting other session when it detects a smart card removal.
We can't explain why it malfunctioned that often, killing session with the smart card still attached or sessions without smart cards at all but disabling the policy fixed the issue. We now detect a removed smart card on the client side and kill the freerdp session accordingly.