My development system is OS/x 10.8, Mountain Lion. I run Ubuntu 10.04 LTS Server in a VirtualBox VM and all the development work is done in that server (easiest for the entire team to ensure we all have the same dev environment).
I switched over from a desktop system (Mac Pro) to a laptop (MacBook Pro), copied over my .vbi file with my Ubuntu server and something was different. I had been ssh'ing into the VirtualBox guest without any issues. Set up my ssh keys and an alias. Sweet. But, with the laptop, I couldn't get there from here. The host name couldn't be resolved.
Yes, VB Network mode was Bridged Adapter. At first, the issue was waiting for the DNS servers to refresh the IP address of the guest OS, which was now on a different subnet because I was connecting over Wi-Fi instead of Ethernet.
But, after closing the laptop for the night, the issue was back and I knew it wasn't from switching subnets. A clue was that I couldn't also connect to one of our development utility servers. Checked wireless -- default configuration had wireless connecting to the guest Wi-Fi and not the corporate Wi-Fi. Fixed that, but no love. Flushed the DNS cache and voila; ssh to the guest machine.
Here's the key: on Mountain Lion use:
sudo killall -HUP mDNSResponder
dscacheutils is still present, but doesn't work in all situations. Use the mDNSReponder.