Von dem "Problem" kann schitho im
DF übrigens auch ein Lied singen.
Eine Lösung wäre, dass du ein extra Programm schreibst, das beim Deinstallieren in den Hauptpfad
aller angemeldeten User geht und rekursiv nach deinen Dateien sucht und löscht ... soweit nichts Schweres (@Luckie:

).
Eine andere Lösung wäre, unter NT die Fähigkeiten von NTFS zu nutzen. Sprich: die Datenbank und Konfig-Daten doch wieder beim Programm speichern, allerdings in benutzerabhängigen Ordnern, auf die auch nur der jeweilige User Zugriff hat. Kennst du ja von den Profilpfaden: Versuchst du als Benutzer auf den Pfad eines anderen Users zuzugreifen, erhältst du eine Fehlermeldung.
Und wenn man davon ausgeht, dass der, der das Programm deinstalliert, min. Admin-Rechte hat (kann man ja notfalls auch prüfen), dann lässt sich beim Entfernen auch das Programmverzeichnis komplett löschen.
Mir persönlich gefällt irgendwie die Variante #2 recht gut. Nur weiß ich momentan, ehrlich gesagt, nicht, wie man mit Delphi Verzeichnisrechte setzen kann

, so dass eben nur der Admin, SYSTEM und der angemeldete Benutzer Zugang zu dem Ordner mit seinen Konfig-Daten hat. Aber das lässt sich doch sicher in Erfahrung bringen.
PS: Unter Win98 kann man natürlich die Daten auch wieder beim Programm in benutzerabhängigen Ordnern speichern. Hier spielen aber die Zugriffsrechte logischerweise keine Rolle.