Thanks all for the leads. Hetzner are seriously low priced, impressive.

In the end we've gone for co-location, we tried to avoid this due to the hassles we've had in the past around physical access.

I guess this workload isn't a great fit for the cloud just yet. Maybe some day!