We bought our VPS' from Hetzner btw. Hetzner is a German ISP which provides cheap (starts from 7€ just look at the price page) but rock solid servers. They don't officially support Arch Linux but the installation is trivial.
--- Quis custodiet ipsos custodes?