Presence detection for minions behind NAT not working

Description of Issue/Question

Presence detection for minions behind a NAT is not working. In minions.py we fetch all of the IPv4 addresses of the minions. For minion1 this will be the IP address the master can see. But for minion2 this will be the address the minion gets behind the NAT. Then those addresses are compared to the addresses the master can see from the minions, which will be the address of the NAT for minion2.

I'm not sure how to address this. Any hints welcome!

Setup

minion1 is directly connected to the master. minion2 is behind a NAT.

Steps to Reproduce Issue

Let both minions connect and fire a salt-run manage.alived.

Then you will see this:

$ salt-run manage.alived
- minion1

While this was expected, since both minions are connected:

$ salt-run manage.alived
- minion1
- minion2

Versions Report

Salt Version:
           Salt: 2018.3.0
 
Dependency Versions:
           cffi: 1.5.2
       cherrypy: 3.6.0
       dateutil: 2.4.2
      docker-py: Not Installed
          gitdb: Not Installed
      gitpython: Not Installed
          ioflo: Not Installed
         Jinja2: 2.8
        libgit2: Not Installed
        libnacl: Not Installed
       M2Crypto: 0.29.0
           Mako: Not Installed
   msgpack-pure: Not Installed
 msgpack-python: 0.4.6
   mysql-python: Not Installed
      pycparser: 2.10
       pycrypto: 2.6.1
   pycryptodome: Not Installed
         pygit2: Not Installed
         Python: 2.7.13 (default, Jan 11 2017, 10:56:06) [GCC]
   python-gnupg: Not Installed
         PyYAML: 3.12
          PyZMQ: 14.0.0
           RAET: Not Installed
          smmap: Not Installed
        timelib: Not Installed
        Tornado: 4.2.1
            ZMQ: 4.0.4
 
System Versions:
           dist: SuSE 12 x86_64
         locale: UTF-8
        machine: x86_64
        release: 4.4.73-5-default
         system: Linux
        version: SUSE Linux Enterprise Server  12 x86_64

But since this was introduced in 2015.8.0, this should be faulty all the way down.

Start in salt/utils/minions.py at the address checks around lines 643, 666, and 667, then reproduce the issue with one directly connected minion and one behind NAT using salt-run manage.alived. Trace how addresses are gathered and compared. Done means the command reports both connected minions, including the NATed minion.