A system for establishing an Internet Protocol (IP) connection with a terminating node includes an originating node capable of initiating communication with the terminating node. The system also includes an intermediate node located between the originating node and the terminating node. The originating node is capable of initiating communication by either (a) requesting communication with the terminating node via the intermediate node, or (b) notifying the terminating node of incoming data independent of the intermediate node. In this regard, when the originating node initiates communication in accordance with (a), either the originating node or the intermediate node is capable of notifying the terminating node of incoming data. Upon being notified of incoming data, then, the terminating node is capable of registering with the intermediate node to thereby establish an IP connection between the originating node and the terminating node via the intermediate node.