Fixed the problem myself. I am using a FritzBox Router with DNS Rebind Protection. Whitelisting plex.direct as described here fixed the problem.
Anyway it is interesting, that the problem only occurs when connecting from an Android device. Hope it assists you in future develoment.
