You mentioned nmap... Have you tried something like 'nmap -sF -P0 -p 1-65550 -vvv -O <ip-address>' ?

There are lots of little ways to discover machines on a network, most of which require a good...