Die Frage ist, welche Adressbücher auf dem Server, der die Mails entgegen nimmt, eingetragen sind. Entweder über DA (Directory Assistance) oder in der notes.ini.
Wenn ihr einen Directory Catalog habt, würde ich mal drauf tippen, dass ihr auch DA eingerichtet habt und die Probleme daher rühren.