Hi,
since nobody answered my question, I will answer it myself.
The reason is actually really simple to tell, if you take a look at my setup and the date I posted the question, because afaik the EE will be released in version 20.10.0 on next Monday. This means we installed the CE under the Enterprice License, which has one big difference to the EE: It always uses a User Mode robot, but for an unattended robot with UI interactions you need to use a Service Mode robot (exceptions might be possible). I myself find this fact not well enough documented, eventhough you can find it in the UiPath documentation (see here: According to Deployment and in my opinion the best explanation here: User Mode VS Service Mode - #8 by radutzp), but its just not prominent enough for me.
I want to add, why we went for the CE eventhough we had the EE license in the first place. First, we obviously didnt know the difference in robot modes. Second, we couldnt get the connection to the Orchestrator having the UiRobot service registered as a Windows Service. This was only hard to fugure out, since we didnt know the service was differently registered. The reason was, that the service was going through the proxy as user service but not as a system service. There some good resources how to configure it to use the proxy though (see here: Redirecting Robots through a Proxy Server). We went with opening the firewall however.
I hope this helps someone with a similar problem. When I was researching it, I read a lot of solutions for the problem (including the ones mentioned in my question), but almost nobody pointed out the problem with the User Mode robot, eventhough some poeple clearly stated that they were using CE, which I find a bit odd. Instead I found those totally unrelated solutions as the ones I tried and some poeple explaining that in unattended mode you can only use simulated clicks and window messages (which might be true for CE). I only figured out that also normal clicks are no problem with EE, because I was researchching how to perform a double click with simulated clicks (thank you @johannes.kusber, see here: Problem with building an unattended bot with mouse actions - #6 by johannes.kusber).