I was having such a hard time getting MS Virtual Server setup so that my virtual servers could access the public network and vice versa.

In the end the problem was caused by a service that is running to enable my VPN connections.

The service is called:

Cisco Systems, Inc. VPN Service.

As soon as I turned off that service, everything with my virtual servers network worked just fine.