The issue was the cpu power. The VPS hadn't got enough cpu time for fullfilling all these requests. The machine reportet 8 cores, but load didn't cross the 4 - mark.
Memory is 4GB, but that was more then enough.
On the top list you were able to clearly verify the php processes running and trying to fullfill the request.
They should take a look at mod_pagespeed (https://developers.google.com/speed/pagespeed/module) and start using a CDN.