Sooo, today I did some researchy things and found out that we can get a server for the same price as on HE from DE.Punkt, and they have newer Ubuntus too:
https://www.de-punkt.de/vserver.htmlWe could have one for significantly cheaper from them (9 Eur instead of 13) if we only take 1GiB of RAM though, which might be worth considering. I also like that they apparently don't bind you for a year at a time, but on the other hand I find it difficult to get in-depth information about their offers (e.g. what this "Fair Flat" traffic option actually means... Host Europe defines the limits very clearly (and generously).
On the HostEurope side of things, it is very probable that we can get one of the new servers with 2GiB of RAM for the same price once we switch to a new OS, and maybe they'll switch us over sooner, too (they did that once before). I searched around a bit for information on when they will have Ubuntu 12.04 available, and they tentatively say Q1 2013, so there is hope yet. It's still weird that it would take them so long, though.
Next offer: Hetzner.
http://www.hetzner.de/hosting/produktmatrix_vserver/vserver-produktmatrixThey look much more professional than DE.Punkt, but also more expensive. Our customary 13 Eur/Month would buy us 1GiB of RAM and 40GiB of HD space and a 2TB traffic limit, though after the 2TB we'd still not pay more and only get throttled to 10MBit/s. There doesn't seem to be any automatic backup included (you can buy it for 5 Eur/Month extra).
Digital Ocean... They look interesting. Their website is too big-soft-button-y for my taste, but the prices look good and they do include backups in the deal. The 99.99% uptime guarantee is nice, but I'm not sure how realistic it is - and the only thing you get if they don't uphold it is a refund for the hourly hosting cost if I understand correctly, so if they don't manage to keep below the one hour per year downtime and keep us down for an entire day instead, they'd refund us 36 cents (on the smaller package). Anyway, I might set up an account with them for testing.
Edit: Oh yes, I should mention: Currently I'm leaning toward staying with Host Europe, but looking into Digital Ocean as well.