I guess one solution would be to put the request on hold and serve it as soon as enough slots are open. Or isn't this a problem?
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).