If you're having trouble with networking on both the host and guest machines, and are running Microsoft Virtual Server 2005 on a broadcom network card, the chances are that you're running old drivers. Update them directly from the broadcom website and you should be good to go.
Interestingly it appears that IBM, and Dell, are still distributing installation aids with the older drivers, which cause issues in this situation.
To be relatively technical it appears that arp packets aren't responded to or sent out correctly. 
 I say this, but I have no network dumps to back this hypothesis up. At present all I have is the experience of debugging the problem and watching the ARP cache of each machine affected fill with invalid entries.