VLAN's and Virtual Appliances in the same environment as the guest machines to facilitate routing should allow for scale without costing these virtualization providers too much.