What you are probably seeing is that NMAP is only scanning "popular" ports by default. You can tell it to scan everything if you want by using the -p option, such as:

% nmap 1.2.3.0/24 -p1-65535

Since people don't normally run "interesting" services on most ports, they aren't scanned by default.

If you have control over the upstream, as in, all the WAN connections funnel through a single connection to the Internet, you might want to use libpcap to tally up traffic and look for this kind of thing. With a bit of effort, you could probably configure Snort to do the job of looking for "unauthorized" servers, provided you can express that sort of thing in the config file. Perl might help here, to generate the rules text.

Snort is actually better because if the deviants on your network discover how you are ratting them out, they could get clever and block your IP. When you scan them, everything could look OK, but in fact they are merrily running a 32 player Unreal server shielded from view. If the traffic is on the network, Snort can find it. In a switched environment you just need RMON support, but virtually every switch supports this for diagnostics.

Either way, once you get your raw data from NMAP, or Snort, or even Perl itself, the next step is to turn it into useful reports, no?