Estou executando o tcpdump 4.0.0 e o libpcap 1.0.0 integrados no Mac OS X 10.6.2 e parece que posso me safar disso:
'not (src net (10 or 172.16/12 or 192.168/16) and dst net (10 or 172.16/12 or 192.168/16))'
Executei alguns testes rápidos que pareciam fazer o que você está perguntando: o tráfego de e de qualquer sub-rede de endereço privado do RFC 1918 foi omitido, mas todo o tráfego em um ou nos dois pontos de extremidade tinha um endereço público foi incluído.
Observe que você teve um erro no seu filtro original para a rede 172.16. Você havia movido a máscara de sub-rede 4 bits na direção errada. 172.16 é na verdade um / 12, não um / 20 como você escreveu. Ou seja, 172.16.0.0 - 172.31.255.255 são todos endereços privados da RFC 1918, enquanto o seu filtro estava capturando apenas 172.16.0.0 - 172.16.15.255.