Ich denke, ich habe die Ursache gefunden.
Ich hatte die Einstellungen / Änderungen immer brav in der names.nsf des Admin-Servers vorgenommen und dann auf dem Traveler-Server mit Pull die Änderungen gezogen, damit ich nicht immer warten muss bis der Server es automatisch macht.
Irgendwann dachte ich, ich schau mal in der names.nsf des Traveler-Servers nach und siehe da, dort gab es doppelte Einträge (keine Replizierkonflikte).
Nachdem ich die doppelten Einträge beseitigt habe, ist das Problem nun weg.