I use RDC, but I only access it through VPN which takes away a lot of routing issues (actually, port 3389 is not accessible through my firewall for security reasons).
Here is the run-down, you need to have the port accessible to an outside request:
HC = His Computer; YC = Your Computer; YR = Your Router; HR = His Router; YISP = Your ISP; HISP = His ISP
Here is a guess of the path of communication to initiate the connection:
YC -> YR -> YISP -> HISP -> HR -> HC
The following is under the assumption the above true:
As you can see, it is outbound traffic as far as your connection is concerned, which is rarely blocked unless you are behind a corporate firewall. The issue is that it is inbound to him, in which case, unless you changed the default port, you need to forward Port 3389 to his windows machine.
Bridged Networking is the easiest way to give the VM a port that can be accessed (it gives a seperate IP to the VM, versus the Mac acting as a router). If you want to use shared networking and forward the port by manual settings, you will have to configure the natd and ipfw services. Unless you need to use shared networking, just going with Bridged will make your life much easier.
In summary, if he has his own external IP, that is, his ISP does not have him share it, you will most likely be able to get to his router. In which case, you will need his router to forward the port 3389 to his Windows VM's IP address. If you get that working, you should be set.