Unfortunately VNC is not an option as most VNC clients use a similar networking mechanic where the client side will open a random port for the outgoing requests, which basically presents the same issue as I have with my solution...

Also, I want to use this on an Android device and grabbing frames from the FrameBuffer in Android (which VNC does) is painfully slow at 4-5 frames per second. The application that I am developing utilizes one of the newer APIs in Android, that allows streaming of the screen content much more effectively (~30 frames per second).

I investigated what TeamViewer does and it seems that they have a server side application that actively forwards the communication between the streaming server (remote controlled device) and client based on unique user IDs.

This is starting to look like my only viable solution as well, although I was hoping that there would be an easier way to achieve the same functionality...

Also, although it'll be a nice clean way to solve the connectivity problem, VPNs are not allowed in some countries. Many mobile operators nowadays have policies that force corporate users to purchase licenses for private APNs, in order to be able to use VPN connections.

I don't know what the exact reason for that is, but it has something to do with their security concerns and maybe even some old-fashioned greed. Some operators have pretty strong firewall rules and may even go as far as to block SSH tunnels (or any other type of encrypted traffic for that matter - although far less common). Exceptions are made only for well known applications like Skype, Hangouts, etc.