DNS requests not resolving

We faced a strange problem on fs3 of DNS requests not resolving - nslookup would complain that even the default dns server could not be contacted and would time out after 2 seconds.

nslookup
DNS request timed out.
    timeout was 2 seconds.
*** Can't find server name for address x.y.z.p: Timed out
Default Server:  UnKnown

Googling gave many hits on configuring the dns service properly, and advice to run

ipconfig /registerdns

All these didn't work - finally the issue turned out to be a firewall problem after all: TCP/IP filtering was turned on, and ALL UDP packets were being blocked. TCP/IP Properties -> Advanced -> Options tab, TCP-IP filtering Properties, Changed radio-buttons to Permit All for UDP Ports and Protocols. That solved the problem.