Bei Strato hab ich seit etwa 8 Jahren Server gemietet. Wenn es billig sein soll, ist das durchaus okay. Einmal hatte ich bisher einen Totalausfall (Plattencrash) - die Downtime wäre für ein Projekt mit großen Einnahmen grenzwertig gewesen, aber insgesamt kann ich bis auf den etwas unpersönlichen Support wenig schlechtes über Strato sagen - bei Problemen die etwas unkonventionell sind, wirst Du da aber nicht glücklich.
z.B. wollte ich eine Subdomain dort auf einem Managed auflösen, ohne die Domain dorthin zu ziehen -> unlösbar
Hetzner kann ich z.B. empfehlen - bekommst recht viel Hardware fürs Geld, aber die wirklich low-Budget Server sind etwas rar. Habe dort akutell einen Shop gehostet und die Hotline ist deutlich kompetenter.