What Would You Want In a Large-Scale Monitoring System?
In addition to rolling your own Nagios UI, there is Nagvis http://www.nagvis.org/ for Maps. I was using a much earlier version, but the latest versions look much easier to implement and very promising. I have also been known to use Cacti with Nagios watching the RRD files every few min so I can still get my performance monitoring while letting Cacti do all the work. I had Nagios check the Cacti RRDs because Nagios has better options for communicating events.
More On Detecting NAT Gateways
Actually, these kinds of fixes have already been done. They showed up in March on slashdot about how to fool nmap. The slashdot article here also has a link to the original paper which talks about tools for various flavors of BSD. There weren't tools for linux, although now there probably are. So, no hacking required, just install some software someone already created. This fix was made before the problem.