The program was probably removed incorrectly, or when running.
Or it came with a really lousy uninstaller.
A relatively safe alternative is
RegCleaner
When you start RC you see in the opening window all software RegCleaner has found on your system.
Look for entries with the name of this game you're unable to remove otherwise.
Check the item(s) found, and NOTHING else, click 'delete selected', and all registry keys belonging to the program RC finds will be removed from the registry.
A backup is made in the shape of a *.reg file.
This takes care of most of the program's registry entries.
Now look for remaining items on your drive: the to be deleted program's folder in Program Files , shortcuts in Start Menu, and delete those as well.
Reboot.
Try reinstalling the game.
Reboot.