In CCleaner there is an application option to clean the "Remote Desktop", however, this does not affect the Terminal Services Client (MSTSC.EXE) history - orignally part of Windows XP, but now renamed to the Remote Desktop Services client v7 available as a free download, used for Remote Desktop & Terminal Services connections.
support.microsoft.com/kb/969084
It stores its connection history in:
[HKEY_CURRENT_USER\Software\Microsoft\Terminal Server Client\Default]
This is not currently being cleaned by CCleaner - it would be great to include into the next release
Many thanks
Yupo