I always use Ccleaner and its registry cleaner.Both after installing/uninstalling games/programs
Something is amiss here... Security Essentials does not ask you to do a scan when you log into Windows. Now, if you haven't done a scan in quite a long time, it might show a small red icon in the Taskbar, but that's all. After you run CCleaner on the registry, I would also suggest a Malwarebytes scan.
I kept getting the yellow icon. Which was really annoying. Well.... My computer was clean only did a clean reinstall 2 days ago, and I always do a regular scan now and then.
If you continue to see the message after you clean up the registry, you probably want to do a AV/Malware scan.
Well... I won't be seeing it anymore. Did a complete reinstall since I couldn't remove the registry entries manually (last resort). But at least it keeps my skills alive