Ich kann Strato empfehlen. Ich hoste dort auch schon seit ca. 2-3 Jahren und hatte noch nie Probleme.
Bei vServern weisen die Strato-Leute per e-Mail sogar darauf hin, wenn der Server ein Kernel-Update kriegt und deswegen neugestartet werden muss. Meist liegen die Zeiten zwischen 8 und 9 Uhr frühs. Das passiert etwa alle halbe Jahre einmal.

Natürlich ist Strato nicht gerade der günstigste Hoster. Der Support kommt mir dennoch sehr kompetent vor.

OVH und die Tochterfirma Isgenug sind auch sehr empfehlenswert. Die Server dort laufen auch sehr stabil. Zum Support kann ich allerdings nichts sagen, da ich den nie gebraucht habe.