Which makes matters worse is that it is also a NAT box with DNS and DHCP in it for the local intranet.

You could use this to your advantage. Make use of DDNS (dynamically assigning DNS records to DHCP clients) and then do a reverse lookup on the IP to check if it is in your private domain space.