@Super Fast it is a bit unrealistic to ask a user to do without it for a month as a test.
@hpb are you able to look in the Windows Event Viewer and see if any error messages regarding Norton are there?
You say it happens after a cleaning run by ccleaner. Do you mean an 'ordinary' clean or a registry clean?
If it was after a registry clean did you try merging the registry backup that ccleaner asks you to make when you do a registry clean?
If in some way ccleaner is able to stop NAV just by a clean, I am sure the NAV devlopers would be interested in a report from you as it could mean that NAV's self-protection is not working.
I recall having this issue around 4 or 5 years ago on a friend's computer. In that case, it turned out that NAV itself was compromised by malware which specifically targeted NAV and had nothing to do with CCleaner. All CCleaner did at the time was reveal the issue such that, after running CCleaner, NAV wouldn't start on the next reboot. Just a thought for what its worth.