the only thing I've come across that prevents NAV working like this is a virus. I know you said that you don't trust the free ones, but it may be an idea to try one like AVG & scan your hard disk with that & see what it comes up with. You could also try scanning with Adaware or Spybot. My thinking is that something has altered a registry entry that is staying "sticky" even when you uninstall and that is preventing NAV from working when re-installed.
- or I could be barking up totally the wrong tree altogether
(I use McAfee).