Hi
I think they certainly could, but probably don't, as it's not a web server or other prohibited service per the service agreement. I would call and find out if they block them just to be sure, and ask specificaly for the range of ports that rdp uses.
To rule out incorrect settings, I would try rdp out on a local lan (switch, hub, router, crossover cable) so you have direct contact with the system, and can set a static ip on both systems just for the test, the one you use to rdp, and the one rdp'd into. This will rule out networking, so you can verify the boxes are set up for rdp correctly.
If the remote boxes are behind routers/firewalls/ICS-ICF, you will need to poke a hole into the routers/firewalls/ICS-ICF, allowing access by the correct ports to the boxes. Like I said, set up a lan and test each box out if you can. Each rdp client needs to have a distinct password, if you don't have a password you won't get far. Sorry if you have a pw already, just making sure.