Some time ago I had to port scan a network which happend to be mostly filtered out and in general rather scarcely populated. When I have started the port scan I had realized that my uplink connection regularly suffers from packet loss as high as 20% and there was no way to fix it in a foreseeable future. The next insight was this: there is no way for a port scanner to produce reliable results under these (and even more favourable) circumstances. So I have tried to quantify the reliability of the results of the port scan exercises carried out over the Internet.
Nmap tries to detect packet loss, but I could not find a concise description of how its packet loss detection really works. I understand nmap does something about packet loss (accidental or rate limiting) when scanning responsive targets. Otherwise, it sends 2 probes with interval of 2 seconds and assumes nobody is home.
Considering nmap's behaviour and 4% typical Internet packet loss , we can calculate that 1 in 625 open ports will not be detected by the scanner, which is not so good already. The things should get worse if we consider impact of BGP route convergence, as soon as I get some useful statistics I will try to quantify it as well.