The problem with those providers is, that the additional IP is usually L3 routed to the physical hosts IP.
A better solution would be to get a /29 subnet or similar, where the gateway is handled by the provider and then configure that subnet on a specific VLAN which is available on all hosts where you want the VM's to be able to run.
More work for the provider, since they have to setup the gateway IP within the /29 subnet on their router and then configure the VLAN on the switchports towards your hosts, but its the best way to make the VM's agile.