How do I uninstall Norton Internet Security 2005 and clean up all its registries?

It comes with its own uninstaller.
This is the recommended route as using the add/remove option can cause problems.

A good free registry cleaner is CCleaner, it also removes other junk files from your system and can be used to clear up the startup programs.