Linux IP Tables has all kinds of cool stuff to overcome that issue.
With lots of configuration, you can overcome some of the problems. But you'll never get it working as smooth as it would without NAT.
B/c neither device can host a server
And the reason for that is NAT. Also, the definition of a server is unclear in the first place. Not all protocols are client-server protocols. Do you call every listening end of a TCP connection a server? Historically some protocols including FTP and X11 have been listening for connections on the client device. And peer-to-peer protocols need to transfer data between two devices, neither of which would be considered a server. In many cases UDP has been used in scenarios, where TCP would have been better suited. The only reason being, that it is easier to punch holes in a NAT, if you are using UDP than if you are using TCP.
You obviously do not understand NAT very well.
I have written a NAT implementation from scratch. What background do you have, which gives you more knowledge about NAT than writing a NAT implementation from scratch?
A correct design would be to use a service that you can query quickly using disparate network connections
Such a design is never going to work. What are you going to do once you face the requirement of notifying the user about an incoming message within a five second deadline, while your power budget does not allow you to send packets more frequently than once every 30 seconds during idle time?
that is all handled transparently by the network, and the software should be able to manage keeping itself going even as its IP address changes
With current network design, changing the IP address is not going to be transparent to the application. Change of IP address will cause ongoing communication to break (or even worse - stall). The best you can do is for the application to notice the IP change and establish a new connection. That will however only work reliably in the absence of NAT. You can do it more transparently to the application, if you are using MPTCP. But that doesn't change any of my points, it just moves some of the logic one layer down the stack.
NAT also has a lot of benefits - including privacy.
Another common misconception. All of the perceived privacy you would get from using NAT can be achieved from IPv6 privacy addresses. You get additional privacy that way, because moving from IPv4 to IPv6 eliminates the leaks you'd otherwise get from the IPID field in the IPv4 header.