A short update..
I have checked with the DNS admin and we have done the following.
We added the ServerA/Acme1 and ServerB/Acme2 entries to Windows 2003 server's host file (the server which hosts the Blackberry/CIG and BES).
Now, when I try to choose the ServerA/Acme1 from the list, I do not get any error and the users are listed. But when I try to type down the ServerB/Acme2 name, I get the message:
"Your Address Book does not contain any cross certificates capable of authenticating the server."
But the servers are cross-certified and they are communicating each other ..
Obviously, BES doesnxxx8217;t figure out that the Domino servers are cross-certified.