This link should have a complete call: SIP Trace - FreePBX Pastebin
I was finally able to go to the remote office and try to dial out from one of those phones and the result is very strange. You dial any number (internal or external) and the phone starts ringing as if the call is going thru but Asterisk does not show any activity on the CLI.
I have checked both firewalls and there is no SIP ALG active on either side that could be modifying SIP packets. Like I mentioned before, if I take the phone to the main office it works fine with no changes.