Si andas pelado de pasta, lo mejor quizá en relación calidad/precio/problemas es OVH, pese a los malos comentarios que ha recibido:
http://www.kimsufi.com/fr/
Si no necesitas potencia, pero sí bajas latencias, tienen unos VPS situados en Madrid que seguramente den muy buen ping
http://www.ovh.es/vps/vps-low-latency.xml
Incluso van a sacar una gama de servidores para juegos, según dicen en su web http://www.soyoustart.es/
La competencia de estos se llama Online.net. Son un poco más tocapelotas, pero tampoco van mal. Cuando digo tocapelotas es que estos sí miran qué uso le das a tu server. A mi me han dado un toque por abrir demasiadas conexiones. Se nota que monitorizan mejor su red. Para un servidor de juegos esto no te afecta en absoluto
http://www.online.net/fr
Y la última que tenía en favoritos se llama Digicube. Ni puñetera idea de como son, es otra alternativa más.
http://www.digicube.fr/rapidserveurs