Are they going to charge you a different rate for the VM servers? Virtual servers are actually a good idea, they provide a perfect snapshot of your system and they can be ported to another server on the fly. I thing virtual servers provide a good business continuity strategy.
Do you have any heavy IO (disk/memory) applications runing on your servers? If so you might have some performance issues and/or some race conditions in your software depending on the type software that runs on the server. Also remember that you can’t have special hardware access via virtual server for example diologic cards or hardware of that nature can’t be accessed. All those things have to be taken in consideration.
Depending on what you have today make them show that you will get at least the same level of service, i.e. if you run any HA/cluster/load balancing make them show that it will really work in virtual environment, if, as already mentioned, you have heavy I/O change your SLA to include at least minimal I/O performance agreements AND how to measure it. Virtual environment can be very good but it is different, much more is shared than just your own systems and not all data centers understand that yet.