This isn't acceptable unfortunately. VMs are meant to run for quite a reasonable amount of time, so we'll be waiting very-very long until slots get available...
Basically what is needed is to find the list of VM migrations needed to be done to free enough space for a new VM (of course, if it's ever possible).