The problem as you stated feels like it should be solvable. The CAP theorem is not relevant here -- you're not bound by strong consistency because you don't need to provide connectivity 100% of the time. There is strong geographical stickiness in connections, so that looks like something to exploit. Combined with smart localized buffering of packets near the destination, it looks like a solution should exist.
The solution may not be compatible with your existing semi-centralized solution, which may be blinding.