I always just do everything by hand. Usually only need to delete the programs that are starting themselves automatically when I book, and some search page redirection in I.E. that Ad-Aware doesn't catch.
If my registry is too fucked up I figure its time to just re-format anyway.
Did a quick google search though and you might wanna check this out:
http://www.glocksoft.com/aatools_registry_cleaner.htm