M,
According to what uninstaller you use, you could try its forced uninstall mode. Revo Uninstaller has such a mode (at least in the paid-for version). You only have to type the name of the software, and hopefully the place where you installed it, and it will try and hunt for it.
One alternative (or additional measure) would be to launch a system-wide search for files bearing the application’s name in a program such as Everywhere. Also, searching for the program’s name in the Registry (more dangerous ; make a restore point before).
The behaviour you describe is strange, to say the least. What uninstaller do you use ? Are you sure you used the audit mode correctly ?