1) Клиентам планируется предоставлять только Linux?
Если да, то OpenVZ оптимален, т.к. имеет минимальный overhead:
habrahabr.ru/post/177423/
Если клиентам нужны другие ОС, или Linux с собственным ядром, модулями и эмуляцией оборудования, то OpenVZ не годится.
2) Биллинг уже выбран? Если да, тогда смотрите, с какими продуктами он умеет интегрироваться.
3) Миграцию виртуалок, отказоустойчивое хранилище данных и т.д. делать планируете?
Если да, то чистый KVM или OpenVZ вряд ли годится, т.к. потребует слишком много настраивать вручную.
Смотрите в сторону Proxmox или OpenNebula:
www.linux.org.ru/news/opensource/9195848
(много ЛОР-срача, но есть кое-что полезное).