Looking a bit more at the request behavior I notice that those slow loading requests succeed in 30s intervals which correlates with the standard PHP timeout.

However it's not always that a fetch.php request will take long. The first fetch.php for wiki_administration:tick.png returns in a reasonable time of 274ms.
I still think there's something fishy going on at your provider and their answer of "we don't actually know what our servers do but please give us more money" does not spur confidence in their abilities.