Also ich würde ja mal schwer annehmen, dass das Ding sich noch als installiert ausweist, weil in die Einträge in der Windows Registry nicht gelöscht wurden.
Also:
Start>Ausführen>"Regedit" (ohne Anführungszeichen eintippen; bei Vista einfach ins Explorerfenster "regedit" eintippen.)
Das "heroes"-Verzeichnis müsste unter
HKEY_LOCAL_MACHINE/SOFTWARE/New World Computing/Heroes of Might and Magic IV/
liegen.
Eine
Empfehlung die ich zur Neuinstallation gesehen habe sagt:
...then uninstall your game, and delete the entire New World Computing key and all subkeys before reinstalling.
Also auf deutsch: Den gesamten New World Computing Zweig aus der Registry entfernen (ist aber vielleicht Problematisch, wenn da noch andere Spiele untergeordnet sind, in dem Fall würde ich mal versuchen nur den Heroes of Might and Magic unterbereich zu entfernen.)
Auf Registry-Editierungen gebe ich alleridngs keine Gewährleistung, und in jedem Fall empfielt es sich, vorher ein Backup zu machen.
Sollte aber eigentlich funktionieren.