When we say ‘pub’, what we really mean is ‘a peer available to peers outside of the local network’, don't we? NAT is a concept from the IPv4 world, and it only concern incoming connections. IPv6 peers – whether they are pubs or clients – may be available to anyone with an IPv6 connection. The same goes for cjdns, yggdrasil, etc.

My IPv4 address is NAT'ed (but I have opened for the relevant port in the router and I have a static IP address, so…), but even if it weren't, my sbot would still be able to reach out to any other IPv4 peer (that accepts incoming connections, whether a pub or not) that it has heard about on the grapevine.

I haven't been following any pubs for months, and I don't feel like I'm missing out on messages (and several tallyings of unique IDs, that I'm too lazy to search for now, seem to confirm this).