I will be speaking about remote pair programming at Pivotal Labs NYC on 08/02 at 12:45. If you can't join us in person join the livecast: http://www.livestream.com/pivotallabs
The limiting factor for desktop screen sharing is usually the upload bandwidth of the host rather than the download speed of the remote given that most (home) internet service packages are high download/low upload. For example, I have 60Mbs/down service and it didn't matter because our office had a completely saturated upload pipe. Thus my sweet download speed didn't help as a remote person.
If possible, upgrade the upload speed of the host or even arrange the pairing such that the person with the most upload bandwidth is hosting the remote pairing session. After an office network upgrade to 20Mbs/up desktop screen sharing -- that is, GUI-based and not ssh/tmux based -- is extremely fast and completely usable.