Thanks guys for the responses.
Let me pass through all the ideas and to give the answers:
1. The connection documents on both servers (Blackberry/Acme1 and ServerB/Acme2) are OK. The possibility of old IP address of one of them is zero because the servers have the same IP addresses forever. Anyway I cleared DNS cache on both servers but no change.
2. First, I cross-certified the servers at domain level and when I got the error regarding cross-certification, I recertified them but I have done it at both levels now - Domain and Server level.
3. Trace command works good on both servers and I can trace one from each other.
4. I installed notes client on the server which hosts Blackberry/Acme1 and can connect to ServerB/Acme2 from that server without problem.
5. Replication is working properly, it is set to push names.nsf from ServerB/Acme2 to Blackberry/Acme1 each 120 minutes. The replication log don't give any error, updates are there, and also when I force the replication using the console, everything is going through.. so the replication works.
6. Domino logs on both servers are not giving me any notifications or errors regarding the other one.
7. DNS records. I must check it with the DNS admin, but if all above is working, I doubt that DNS is making troubles.
9. Again, I must repeat, that the user from the server ServerB/Acme2, who was previously added, is still running fine on BES. I asked her today if there are any troubles with messages on her Blackberry and she confirmed that everything is OK. Also, log on BES is telling me the same.
Pretty weird situation....
Anyway, I will check the DNS today and will report of any change.