mstsc allows you to save your credentials for a system so you don't have to type them in every times, which is nice when you use randomly-generated long passwords.
My Server 2008 machine allows this just fine, but on my Server 2003 system it fails, with the message:
The system could not log you on. Make sure your User name and domain are correct, then type your password again.
I'm positive the credentials I'm saving are correct, and when I type it in by hand it works.
Try saving RDP files using MSTSC. There may be a bug with caching them and selecting the servers from the drop-down menu.
How about looking here? Microsoft