I would perhaps help to know what the other Guests are - I mean, you say they are affected. Although ...
You probably have something horribly wrong in your networking configuration. The previous answer was explaining the matter. I will add to that a few things:
- why NAT stops working, well, don't know about when it really does it, that's why I used the word "horribly". But you didn't explictly say that NAT Service is shut down.
- Guests are often copies. IP changes when you boot it up in DHCP, but the identity doesn't if you didn't say "I copied it". The NAT is confused with that. Then the others do not work. If they are ALL copies, there you go, only one works (if even that).
- why a reboot cures the problem, it may simply be that you have different computers active after "a reboot"
- you CAN have the same identity with different Guests, but they cannot be active at the same time
- if you have fixed addresses, that may cause another possibilities for same IP's for different computers
- if you have fixed adresses, but the IP-range is wrong, gateway is not found and thus internet does not work
- does something like file sharing work? Ping is NOT the same thing. If file sharing (or something like that) does work, only the gateway is wrong.
In the above, there is at least one possibility why it *looks* like NAT is not working for "any computer" and why reboot "cures" the problem - or so that it seems, but the reality behind it is not really that.
I assume that your Guests are not all in the same directory ... if they are, then all kinds of things are possible. Basically, one VM computer = one folder, everything else is just wrong (in the normal case when you don't have shared virtual disks among VMs). However, this does not really explain your case, it's more like a conspiracy theory.