Sorry I forgot to update here.
It was as I guessed in the end. Another VPS was deployed on the host and was draining it.
We have been moved to another host less than 24h after the opening of the ticket.
Bravo to Contabo 
I would ask the mods to leave these last replies here even if it’s not “discourse” related as it can help others figure out other reasons for which their instance might have problems.