Strange NS behavior on OS X — can't connect to SSH server
Solution 1:
You've encountered the overly zealous OS X DNS Cache. Next time you see this you can flush it:
# sudo dscacheutil -flushcache
That should fix SSH, etc.
Solution 2:
The command in Mavericks and Yosemite (starting from 10.4) is:
sudo killall -HUP mDNSResponder
Source: https://support.apple.com/en-us/HT202516