Have you tried doing “on demand” cross certification?
This would be done by being physically present at the server itself. This would need to be done at both servers>
Firstly you should list each server in the other server’s document in the “Access Server” field.
Launch nlnotes.exe from the domino directory of the server. Ignore any error messages.
Type in the name of the server in the other domain and click Open.
You should be presented with a cross-certification dialog box. You may choose the level of cross-certification (server to server, server to OU, or server to O). Make sure to choose “Local” for the server to create the cross certificate.
You should then find a cross certificate document in names.nsf on that server.
Repeat this process on the other server and you should be all set.
If this does not work, then you may have one server certified with an International certifier and the other one with a North American certifier.