Try this link from Microsoft. It's a utility that will remove any persistent program that doesn't feel like leaving the installation database. I just tried it on my machine and was able to remove some old programs from my Add/Remove Programs list that insisted on hanging around. I've never had a problem with MediaLab or DirectRT in this manner, but it may be a fix for you. If so, it's a very quick and easy solution. Let me know if it helps.
See:
http://support.microsoft.com/kb/290301/en-us
[edited from follow-up email]
Yes, the Microsoft software removal package seemed to do the trick - thanks. I now no longer get the error message and am getting a prompt asking me to send you the code generated by my PC installation.