Alguem sabe do que isso se trata? Alguém enfrenta ou enfrentou o mesmo problema?

Não é possível identificar um problema sem ter acesso ao código e a hospedagem. o que mais existe hoje em dia é malware.

contratamos freelas para desenvolver pequenas aplicações em PHP

Você realmente confia nesses freelas? eles são realmente especialistas? o que garante que o erro não é do desenvolvedor?

Tanto o VPS quanto compartilhada teve o mesmo problema

Por esse comentário tenho 98% de certeza que o erro não é da Hostgator, e sim da sua aplicação. Alguma coisa mal configurada ou alguma lib maliciosa instalada.

A solução seria montar meu proprio servidor LAMP e fugir das hospedagens prontas?

Se até em VPS deu problema não adianta colocar em servidor on-premise, AWS, GCP, Azure, qualquer local que seja. Tem que investir em um especialista para fazer uma revisão de toda a sua aplicação. identificar exatamente qual é o malware, como ele está sendo introduzido na sua aplicação e como se proteger dele