If no regcleaner will work, then a reformat might be in order. Any type with an uninstall utility attached to it should work. Something else you could do is download system mecahic and try the uninstall cleaner on it. Going to the regestry and manually removing the entry should work also. It sounds like what you did was delete files without uninstalling it.
I know what you mean about the little things driving you nuts. I go through that all the time. I am a perfectionist when it comes to my pc, if one thing is out of order I fix it till it's perfect, if that don't work, I reformat and start over again .. That could explain why I know so much lol .