I started having a problem when upgraded a second server to R6: scheduled replication and mail routing failed due to public keys not found in Address Book. The failure was between an R6 server and the one previously upgraded.
Before the upgrade I had set up servers to compare public keys and they were working ok. I had to disable this feature to restore communication between these two servers.
I found (on Knowledge Base) that in the past similar problems have happened when upgrading from R4 to R5. Is someone else having these problems and if so, have you got it to work?
Strange thing is communication between these two servers when one was R6 and the other R5 was ok. Problem started when the second was upgraded to R6!
The two servers are one on an NT4 box and the other on Linux RedHat.
TIA,
Michelangelo
Subject: no server to server communication: “Your public key was not found in the Name and Address Book”
Have you run the usual compact -d, fixup and updall -r against the names.nsf to fix any NAB corruption?
Also, If a server document is corrupt, just copy it back from the copy of the names.nsf you made before the upgrade took place … I am just assuming you made an archival copy of your domino data before the upgrade took place 
If not restore names.nsf from backup and then copy documents across. Failing that, you may need to copy the public key from the server.id and then copy it back into the correct server document in the Directory. You may need to do it for both.
Jaime
Subject: RE: no server to server communication: “Your public key was not found in the Name and Address Book”
I had similar trouble. One of our recently upgraded Notes servers would not communicate with only 2 of our R5 servers. I was able to resolve by cutting and pasting the server doc.
Hope that helps,
Nick Schott
Subject: RE: no server to server communication: “Your public key was not found in the Name and Address Book”
Here is the related article from Lotus:
http://www-1.ibm.com/support/docview.wss?rs=463&context=SWD10&q1=Your+public+key+was+not+found&uid=swg21087840&loc=en_US&cs=utf-8&lang=en
This problem is under investigation.
You have to change the Notes6 Serverdocument (Security Tab) that Notes doesn´t compare the public keys (Default is no).
Pasting the foreign Server document in your Addressbook is the another option to work around this behavior.
Greetings
Andreas