The problem is that with VNC as well as SSH, the IP on GPRS is not a public IP - so connections to the device from outside are not easily done.

I like the idea of doing this through VPN, and would love to see what you have done to see if I can modify it for our needs...my concern is that the devices still need internet connectivity - and if they are on our VPN and allowing an ssh tunnel through that way, I think we will eliminate their internet access, but I need to confirm this.