This is a bit of a crazy idea and it would involve some network down time but it sounds like your options are limited by your cheap gateway, with no way to see what's being NAT'd.
Change the IP address of your gateway to something else, then disable DHCP to prevent any machines finding out new gateway address.
Boot-up a machine running ethereal/wireshark taking over the old IP address of your gateway.
The offending machine should come up like christmas lights, now that the machine doing the packet sniffing IS the gateway!
I haven't used chef, but I have used cfengine quite a bit. So while I don't have specific advice for your environment, I can tell you in general how I've handled it. I expect that you can do something similar with chef, puppet, or whatever.
To start, let me say that in my opinion, if you're using chef (or any other configuration management package) to ONLY push packages, then you're missing out on a lot of functionality that could be making your life easier. The well goes MUCH deeper.
In the environment that I manage, I've set up cfengine to not only install/remove packages, but also to maintain specific (and frequently security-related) settings across all servers, across one or more subgroups of similar servers, or on specific hosts, as needed.
This does a couple of things for me -
First, if I bring up a new server, then as soon as it's added to configuration management all of the common and group-specific settings are automatically applied. This means that I don't have to worry about the base lockdown - it's done automatically for me - and I can focus on locking down the applications that are unique to that server. It's like a self-checking checklist, but better.
Second, I can look at the logs and see the results of the configuration runs on every host, including which settings were verified as correct, and which settings were incorrect and fixed. This lets me keep on top of what's happening, but more importantly for compliance, I can parse that information and generate reports that prove the servers are not only configured as expected, but also verified as correct with every configuration run.
This also has a side effect of letting you know if your configuration changes unexpectedly for whatever reason, whether it's a careless coworker, or an attacker that has compromised your system.
So, while it's probably not the answer you're looking for in the short term, maybe it will give you some ideas to include in your long term plan.
Best Answer
I've automated scanning before, but did not use an outsourced scanning service. On the topic of outsourced security services for scanning, many people I know swear by Rapid7. They also have HD Moore on staff so they certainly know penetration testing and Metasploit.
It is trivial to use Nmap or Nessus scripted, encrypt the output and send it to yourself via email.
You could also regularly assess compliance with a hardened baseline to ensure they are not deviating from it over time, or introducing new risks..
If you are a security guru, I'd keep it in house, but otherwise, I would outsource it.
Keep in mind that to get accurate results from vulnerability scanning & compliance analysis, you'll need to perform authenticated scans from inside the firewall(s).