Summary: how do I create an RDC connection from a Windows 2008 server to another server?

Our client will only allow us to connect to their server via a static IP address (which is fair enough), but unfortunately as we're a very small company we don't have one in the office.

As a work around, we had the connection working through our old Windows 2003 server (dynamic-cloud from 1and1). .. however we have just rebuilt the server to run under Windows 2008 R2 (don't ask, but it was necessary), and now I simply cannot get the connection working.

I have added an "Outbound Rule" to Windows Firewall with Advanced Security (TCP, All local ports, 3389 remote port - I have also tried the other way around).

I have added a packet filter IP security rule with the same details.

The 1and1 firewall rules (through their online control panel) allows for 3389 TCP and UDP.

But it is simply not connecting (yes, the server is definitely on and able to accept connections) with the general error of...

Remote Desktop can’t connect to the remote computer for one of these reasons:
1) Remote access to the server is not enabled
2) The remote computer is turned off
3) The remote computer is not available on the network

Is there anything obvious I've missed - or something I can use to find out where the request is being blocked? The new server is using the exact same IP address as before, so I don't believe that would be an issue. Unless it's trying to use an IPv6 address rather than the old IPv4 address that it was before?

I apologise that I am not a network person by trade, but I know more than anybody else in my office!!