Ich hab zwar im F2K "prevent clipping" eingestellt, aber das wirds auch nicht rausreissen.

Mit MP3Gain habe ich vor langer Zeit die Lautstärke viel zu hoch gesetzt

Genau dort liegt das Problem. Zuerst wird die Datei normal decodiert - und zwar mit den Werten, die im Header eines jeden einzelnen MP3-Frames eingetragen sind. Also mit großer Wahrscheinlichkeit stark übersteuert. Diese Decodierung übernimmt nicht F2K direkt, sondern überläßt das den bereits im System vorhanden dll's, Plug-Ins usw.
Das deshalb, weil man ja sonst das Rad neu erfinden müßte. So können jedenfalls diese Bibliotheken von im Prinzip jeden beliebigen Player angesprochen/benutzt werden.
Das heißt, das aufrufenden Programm (F2K, Mediaplayer ...) übergibt die zu decodierende Datei an die zuständige DLL und erhält den Sound fix und fertig decodiert zurück. Erst jetzt würden auf die fertigen (und in Deinem Fall übersteuerten) Samples die Korrekturdaten eingerechnet werden. Und das wiederum bedeutet, das Deine Verzerrungen bestehen bleiben, egal wie die Lautstärke dann weiterhin verändert wird.

Das Problem ist also nicht, das F2K daraus wieder die "richtige" Lautstärke machen kann, sondern die Reihenfolge der Abarbeitung.

Mit MP3Gain habe ich vor langer Zeit die Lautstärke viel zu hoch gesetzt, weil ich es
einfach nicht besser wusste. Also müsste ReplayGain doch eigentlich diese falschen
Werte nach unten korrigigieren (auf die empfohlenen 89dB).

Aber sicher ist sicher, ich werde alle MP3Gain Änderungen rückgängig machen und
dann erst von F2K analysieren lassen.

F2K ermittelt zwar diese Werte auch, schreibt aber "nur" den Korrekturwert in einen Tag. Die Datei selbst wird nicht verändert.

Also mach zuerst die Änderungen von Mp3-Gain Rückgängig und lasse das dann von F2K neu ermitteln.

Es ist zumindest der "bessere" Weg.

Wenn Du es nicht Rückgängig machst, passiert allerdings auch nichts weiter. Da die Datei ja schon "angepaßt" ist, ermittelt F2K lediglich Werte, die um 0 dB schwanken - also keine wirklichen Korrekturwerte mehr.

Mit anderen Worten: Die Werte von F2K werden nur beim abspielen auf die (unveränderte) Datei "drübergelegt".

MP3-Gain verändert die Datei dagegen direkt.

Wenn ich die Funktionsweise richtig verstanden habe, müsste
ReplayGain ja die Änderungen von MP3Gain aushebeln. Oder
erkennt ReplayGain, dass eine MP3Gain Anpassung vorhanden ist
und verfährt dann anders? Sind Probleme zu erwarten?

Ich habe noch zahlreiche von MP3Gain angepasste MP3s, die ich
zukünftig mit ReplayGain in Foobar2K nutzen will.