Simply deleting the Norton Internet Security folder won't harm the system but NIS really hooks into your system... there are tons of Symantec related files scattered through all kinds of hidden and obscure places, not to mention a gazillion registry entries. Tracking that all down to delete those as well is a big pain.
Unfortunately, this may be your only solution in the long run if all attempts to uninstall normally fail. I had the exact same problem when I was running Win2K and tried to uninstall NIS. If you're uninstalling because you need to re-install then don't worry, delete away