Can the remote client connect to any Terminal Server on the Public Internet?
This would be the first thing I would verify. If you do a search on Google
for Remote Desktop Web Connection, many public connections are listed (while
admins should probably block robots/spiders from picking these up) which
could be used to test your connectivity. I'm not recommending trying to
logon to any of them, but if you can get to their GINA Logon then you're
connected over port 3389 and know that the remote computer is working
properly.
Another thing you will have a problem with is a highly latent connection,
regardless of the measured thruput. 20Kbps is barely enough bandwidth to
work over a 800x600 desktop at 256 colors with mediocre performance when
latency is not a problem, but when you add a high latency to the connection
the performance may reach abismal.
The lowest speed connection I've found to be sufficient for a working RDP
session @ 800x600 & 256 color depth is 26.4Kbps.
As far as VPNs go, I not only do NOT recommend them for securing RDP
connection, but believe that unless they are managed IPSec/L2TP VPNs that
they are a security risk as you're allowing any garbage or services on the
remote computer to directly interact with a corporate network. PPTP VPNs add
zero extra security to an RDP Session, as the tunnel is setup with the
credentials provided by the end-user, not by PKI based certificates.
Secondary authentication (i.e. Safeword or SecureID) is a better way to
increase the already solid security of Windows Terminal Server, whether using
RDP or ICA protocol.
Patrick Rouse
Microsoft MVP - Terminal Server
http://www.workthin.com