My host is an out-of-the-box Ubuntu 12.10 simply connected to Wifi.
I installed VirtualBox, and then a few Linux and Windows 7 Pro guests on it, all with default VirtualBox options (NAT).
I reboot them every day.
Yesterday all had network access.
PROBLEM: Today all the Windows guests says "No Internet access".
Linux guests still have network.
As an experiment, I created a new guest VM, installed Windows inside. Result: no network.
All Windows and Linux guests are out-of-the-box, I did no network tweaking whatsoever. Below is their VirtualBox-side network configuration just in case:
(2 years later: exact same problem happened, a VM that was working yesterday... same solution)