Hab jetzt seit einem Jahr ca. einen vServer von

.
Nutze den für einen Teamspeak Server, OpenVPN und paar kleinere Sachen und läuft super stabil.
Für 1,50€ im Monat eine KVM Virtualisierung ist auch sehr nice (im Gegensatz zu OpenVZ).
Hängt natürlich davon ab, was du mit dem Server machen willst. Gibt entsprechend größere Pakete.