Okay, first our setup:
I'm currently working over VPN to a mac mini OSX 10.6 server. We have a testsetup VM running on that, using ubuntu 12.04.
Earlier today, there was an outage because of which our mac mini server was reset. Since then, i was unable to initiate a connection to the VM (which i did boot) -- no ssh, no web, ... . I couldn't ssh or web from the mac mini to the vm either. I could do so from within the VM itself, though. Ping did work on all machines.
Lastly, I tried pinging from the VM to my laptop. It took a moment, but then it finally started to ping (no timeouts or so). After that, web and ssh magically worked.
I then didn't use the machine for about 5 minutes, after which i had to ping from the server to my laptop again before i could setup a connection.
I'm in the dark on what this could be, though I think this is something to do with lookups.