Also, if the device is connected through wifi and then on to internet, the mobile operators have no say in things.
It is, however, a messy area, so if you plan to make it a public app, expect support.
There is one way to solve all the above problems, though it requires more effort.
You set up a server. Both devices connect to your server. This is both outgoing connections, so it will work fine in all environments.
From here on, you have two options:
* The "clean" option. The server simply repeats everything it gets from one device to the other. This means everything passes through the server, which means traffic you'll have to pay for, as well as possible privacy concerns. Basically, it listens on the connection, and repeats everything it hears to the other side.
* The "unclean" option. Once the server has both connections, it can tell each device that it's moving to another address. Now, here's the trick: it instead of telling them about a new address for the server, it gives each device the address of the other device, in effect merging the two connections to one. As both started as outgoing, firewalls and NAT will not be a problem. It's more difficult and I don't think you can expect to do it through a high level API. This is the method Skype use. Basically, it says "Nah, you'll have to handle this yourself", and ties the ends of the lines together and disconnects itself.
Some network admins think the second method is a potential hack attack and go ballistic, but it works, and it works damn well. Much harder to do, though.