Pois a mim demoraram bastante a dar a primeira resposta, depois de eu responder já obtive respostas mais rápidas no mesmo ticket. Eles tem também vps KVM que apesar de serem um pouco mais caros podem ser uma solução para o meu caso.
Também estou a testar o serviço da subnetlabs mas estes tem os servidores na américa do norte.
Para preços baixos na europa não encontrei mais nenhum a não ser o server4all