That was the solution!
I installed the Blackberry manager on my computer which already had Notes client and everything works OK. I am able to add the user from the other domain! No single problem!
I cannot believe that BB Manager installed on the server made me such problems.
Thank you guys 100 times!
You are No 1!!!