The most recent version of the VS 2005 cleanup tool has been posted to this location on the Microsoft Download Center. This version matches the version on my WinISP site as of right now, plus it is digitally signed and posted as an EXE instead of a ZIP file so it does not have to be saved to the desktop and unzipped before you can use it. This version on the Download Center will likely not be updated until VS 2005 releases because it has proven to work correctly in beta 1 and CTP uninstall scenarios. I will update the version on my WinISP site if/when any additional beta 1 or CTP issues are found in the future. We are currently working on updating the uninstall instructions on the VS 2005 site to include a link to this tool and more specific instructions, so stay tuned for that.
5/1 UPDATE: The new uninstall known issues page has been posted. You can view it by clicking this link.