Update: Did tests with two different products of Contabo (VDS, VPS). Both have the same issue. Did a couple of tests, found out its often at specific times of the day (peak) and sporadic behaviour (at non peak times) when 2 downloads are fast and the third is slow.
Also tested now Deutsche Telekom (3 different locations in Germany) and Vodafone as providers.
Turns out, that at the same time I had at least 50-90 times faster speed with Vodafone.
The average download with 30-40 KBps at peak times via Deutsche Telekom for a server with 500Mbps (62,5 MBps) Interface is not acceptable.
Customer support tested on our server vs. speedtest.net. In this case the software connects to the best available server. The server then connected with almost maximum possible speed (https://twzn.de/zazuz).
From my perspective, there is a peering issue between the backbone Contabo uses and Deutsche Telekom. There are a couple of discussions in forums, that seem to confirm those issues since quite a while already.
Looks like I need to move to another hoster. Should be easy peasy with Cloudron, I hope... 🎉
(response from support is still open, will update here)