I was at an event where I ran into NineStar’s CEO and asked him, whether there was someone who could help me, because I had increased suspicion that it was an ISP issue. The following day I got a call from NineStar’s CTO who almost immediately knew what was up. He directed his staff to provide a solution, which is working great. See also my related post.
Thank you very much to all of you for helping troubleshoot!