So apparently my Router has a hardware firewall implemented, which is probably causing the issues. According to the documentation I'd have to open the relevant port (in this case 16000), which I don't want to do due to security concerns. So I guess I will just live with the issue. I mean I can still find games, it's just annoying when it happesn.
Just one remaining question: Is it maybe possible to "fix" the client at least from crashing i.e. shutting down or is it too hard/not possible to find a solution here?

Fowarding the port isn't risky at all, since it's UDP and it's a high-port, which is only accessible by the game process when the game is actually running. Your router won't respond otherwise. So it's not a security problem at all. I can assist you forwarding 16000 UDP in your router. Please paste me the network diagnostics result.

I already did, see page 1 It was all ok, no actions recommended. Therefore it's so weird I am having this issue at all. Ok, thanks for your answer, but if I understood the router documentation correctly, I would have to permanently open the port (not just forwarding) in order to evade the hardware firewall. But I will check that again.

If you show me a screenshot of your port forwarding rule and a screenshot of ipconfig /all, I can tell you, whether things have been configured correctly.