Hallo zusammen,
@Dirk: ja, jeweils mit Löschung der Sync-Daten via Serverkonsole.
Konnte das Problem nun lösen. Die Ursache lag jedoch an ganz anderer Stelle.
Es war nicht der Traveler-Server (der ist inzwischen auf 9.0.1.10 geupdatet - Problem war dadurch nicht weg...), sondern der Sync der Adressen via Mailfile.
(Da der Adresssync bis zum Gerätewechsel klappte, hatte ich das pernames / mailfile erst mal ausgeschlossen).
Da mir nix mehr einfiel, habe ich unter $conflicts im Mailfile geschaut => deutlicher Unterschied zum names.nsf.
Grund war schlussendlich die Mail-Replikation mit einem zweiten Rechner (von dem ich nix wusste), dessen $contacts "etwas älter" und mit Repl-Konflikten behaftet war.
Also: $contacts geleert, deletion stubs beseitigt, nochmal auf allen Clients ordentlich repliziert, dann den Sync der Kontakte wieder aktiviert: alles i. O.
Danke nochmal Euch allen und sorry, dass ich Euch am 'falschen Ende' genervt habe ...
Sebastian