Yes, that was exactly my experience with OVH yesterday — with every telephone format I could think of ever having seen.
I’m back on Scaleway again, trying one of their Docker images (Ubuntu 16.0.4 with Docker 1.12 — actually current!). I’ll let you know how it goes.