Dag, I'm well familiar with the typical configuration, in which the gateway is in the same sub net.
However, this particular setup is actually quite common in the VPS world. At OVH Hosting this configuration is de facto standard. It works by adding a static route to the gateway over the host's IP. With Linux, there's no problem, and actually earlier versions of OpenBSD would probably have worked in this setup just as well. The issue has to do with the ART-based routing which was introduced quite recently if my memory serves me right. Yours, Jyri