Changing IPs can be dealt with network-wide DHT or a known-peer approach.
The NAT traversal shenanigans only have to be successful on one side. When the geek manages to be reachable, they can talk to their grandparent, given they use software that tries to connect them, like RetroShare.
This doesn't cover all cases, but enough to be useful and valuable.