This may not be the best approach, since they have legitimate access to the systems in question. See A practical approach for defeating Nmap OS-Fingerprinting.

What a fascinating article ! Modifying the kernel's tcp stack to fool nmap, that's some level of extremism i had not seen before :)

IIRC there are other more subtly ways of achieving this sort of thing.

Also nmap may not be an option. Yesterday pankaj_it09 asked if it was possible to use Nmap::Parser without having nmap installed on the host system.