Moin,
also all-ink und hosteurope kann ich auch bedenkenlos empfehlen. Z.Zt. bin ich bei ovh.de, und bin mit denen und ihrem Kundensupport sehr zufrieden. Zusätzlich bieten die bei einigen TLD die Möglichkeit, den Whois zu verschleiern. Dann tauchen bei einer Datenabfrage nicht Deine, sondern die Daten von OVH auf. Ist natürlich nicht wirklich anonym, da OVH Dich ja kennt, aber eben auch nicht für jeden xbeliebigen einsehbar, wem die Domain gehört.
greetz
edit: axo, und http://www.bekawe-hosting.de/ soll auch sehr empfehlenswert sein. Habe den mal einem Kumpel empfohlen, und der ist sehr glücklich mit dem Anbieter. Aber da kann Freelander sicherlich was zu sagen ;).