教えて!gooに、同様の質問をしている人がいて、すでに回答が載っていましたので引用しておきます。
参考URL → http://oshiete1.goo.ne.jp/qa3929444.html
mstsc.exeのバージョンですが、有効期限切れとなるものが
6.0.6001.16659 (longhorn_rc0.070916-1443)
ならないものが
6.0.6000.16386 (vista_rtm.061101-2205)
となっています。
ということで、mstsc.exe自体の問題のようです。（問題というより仕様ですね）
質問された方は、
XPSP3を入れたことが原因で、mstsc.exeとmstscax.dllをSP2バージョンに戻したところ、接続できるようになりました。
と書いてありましたので自分も早速実行してみました。
1.別のWindowsXP SP2 PCで、mstsc.exeおよびmstscax.dllを検索。
（このとき、全てのファイルを表示できる状態にしないと駄目です。）
検索しなくても、普通はc:\windows\system32 配下にあると思います。
2.該当ファイルを SP3 RCを入れたPCに上書きでコピーします。
コピー先も、普通はc:\windows\system32 だと思います。
コピー後は、特にOSの再起動も必要なく、すぐにリモートデスクトップが使えるようになりました。
RC版を入れている以上、自己責任ですので仕方ないですが、リモートデスクトップを多用しているのであせりました。正規版SP3が待ち遠しいですね。
