Jeff, there are several viruses that could cause this problem. Nimbda is one and W95.mtx is another. MTX prevents NAV from updating further so that could be why you're running a clean scan.

I just smell virus..