My setup is as follows:

Domain name is fs.my-domain.com. This domain contains 2 A records pointing at IPs for fs1.my-domain.com and fs2.my-domain.com.

Each FreeSWITCH server, fs1 and fs2, runs the same config files and domains for the users are fs.my-domain.com.
They share the same database on db.my-domain.com.

Calls going and out from each respective server, but when a user is trying to call a user who are on the same server calls fails.

It's random which server they land on as the dns is doing round robin dns between fs1 and fs2. 
If two users lands on the same server everything works. 

I will try and get debug info.

On Monday, November 23, 2015, Lyle Pratt <lylepratt@gmail.com> wrote:
We've encountered something like this before and it ended up being a NAT issue. Users could receive calls from the server they are registered to because the registration would open a pinhole in their router. However, they could not receive calls from the other instance (no pinhole). We couldn't find a way around this.

I'm not sure if this is your same issue, but maybe this will help debug.

Regards,
Lyle Pratt