If Your DNS settings are correct, and you reinstalled TCP/IP, you are probably right about a registry key being the problem. The Key that gets removed when you uninstall TCP/IP from your LAN connection is HKEY_Local_Machine\System\CurrentControlSet\Services\TCP.
There are three others that I know of that might cause the problem. This is kind of a shotgun solution but just might work. Disable all connections that use TCP/IP. Uninstall TCP/IP. Don't restart. Export (back-up) and then delete these keys.
HKEY_Local_Machine\System\ControlSet001\Services\TCP
HKEY_Local_Machine\System\ControlSet002\Services\TCP
HKEY_Local_Machine\System\ControlSet003\Services\TCP
Restart, reinstall and reconfigure TCP/IP.
Even though I didn't have your troubles, I tried this on my own WIN2k box and everything reinstalled and worked after. DO BACK UP FIRST though.
Good Luck