In the past, I have uninstalled it via ADD/REMOVE and its own uninstaller within the programme. I have then searched the whole of the PC for NORTON and NAV and deleted anything found. Also search for the word SYMANTEC but just question yourself over anything found since it is likely to be Norton but not 100% positively.
When you think they are all gone, use CCleaner or something similar to scan and correct your registry.
The positives you're getting with McAfee could be legitimate hits or could be the Norton quarantine showing. You need to check the message and note the path.
I'm glad you can get to safe mode, because that is good for getting rid of files and programmes. I would suggest that you try doing what I have indicated above in safe mode.