Primeiramente, se você acredita que este é um problema de fornecedor que eles não estão abordando, eu considero migrar para longe. Dei ao VPS.net o benefício da dúvida quando seu SAN continuou travando (derrubando todos os VPSs no processo), mas depois de alguns meses de "corrigimos isso para sempre" e ainda falhando, eu tive que votar com minha carteira.
É surpreendentemente fácil iniciar uma empresa de VPS (você realmente só precisa de um pouco de espaço de datacenter e alguns servidores) para que eles não sejam todos iguais em capacidade técnica, mesmo antes de chegar ao atendimento ao cliente.
Mas em termos de chegar ao fundo do problema, eu primeiro olharia para parar as coisas acabando em troca. Deixe o swap ligado, mas faça o que tiver que fazer para não empurrar as coisas tão longe. Rein na aplicação Java ou adicione mais RAM. E veja o que acontece. Se isso é muito regular, você não deve esperar muito (ou pagar muito) para ver um resultado.
O mesmo com a CPU. Se você tem coisas rodando a 100% por longos períodos, você quer ter certeza de que elas não estão interferindo com outros aplicativos. A maneira mais simples de trabalhar isso pode ser feita definindo o bom valor de quaisquer aplicativos que sejam desenfreados para algo positivo. Um bom valor de algo como +10 deve permitir que o sistema obtenha prioridade total dos recursos antes de seus aplicativos. Barra lateral: Valores legais basicamente significam que você é mais educado quando se trata de agendamento de CPU. Algo com um valor baixo (por exemplo, -20) significa que eles serão priorizados em relação a todas as outras coisas com valores mais altos.
Se puder, expanda seu teste para outros itens da rede local. Se eles fornecem um resolvedor de DNS (como fazem muitas empresas de servidores), execute ping constantemente (bem, algumas vezes por minuto) e registre os resultados. Se você ainda puder acessar isso durante períodos de inatividade, é menos provável que seja sua culpa.
E como eu digo, se isso não é culpa sua, mova-se. Se você gastar mais tempo tentando consertar isso, você estará superando qualquer benefício possível de ficar com essas pessoas. Eu pessoalmente tenho uma experiência muito boa e longa com a Linode, mas há muitas empresas boas por aí.