At one of my client office, their computers runs under windows 2000.
I needed to access a windows 2003 server with a RDP Client.
Windows 2000 does not have mstsc.exe installed, but the one for windows XP works well with windows 2000.
Terminal Services Client comes in two versions, 5.1 & 6. The 6 needs a Genuinue Advantage validation (I didn't try but I don't think ti's possible under windows 2000 to have this validation), but the 5.1 here :
Run the installer, click next until the end and then WindowsKey+R, type mstsc
et voila !