Personally I would continue down the manual uninstallation route. There isn't any documentation on how to manually remove ISA 2000 so you will have to wing it a bit.
If you have the facility, take an imgage of the server before you start, Acronis trueimage works well for this. That way if you end up in a corner you can image back to a working state.
My approach would be to do as you did and go through the registry removing ISA server related keys.
Stop all ISA related services and remove their registry entries from HKLM\System\CurrentControl
Set\Servic
es\ this kb
http://support.microsoft.com/kb/300879 lists the ISA services - looks like there are 4 of them.
Delete any ISA 2000 related files from your Program Files folder.
Also check to see if the MSDE (SQL) is installed for ISA 2000 and uninstall that too.
Might also be worth removing and re-installing IIS if you don;t use it for anything.
The ISA2006 installer can only be looking in the registry or the file system for evidence of ISA 2000 so it will definitely be one of those areas that holds the key.
If you still can't get ISA 2006 to install, try running ProcMon
http://technet.microsoft.com/en-us/sysinternals/bb896645.aspx as you launch the 2006 installer to see if you can find which files it is looking at. You may be able to identify which lurking ISA 2000 file (or registry key) is preventing the installation.