Parsifal,
One of the problems I found when trying to find a provider was that there are no decent, honest review sites out there. There's a couple of indexes and that, but what people need is a *proper* review site, where the reviewers actually rent webspace (or request a trial), try out the functionality, performance and support, poll users, etc. and give an unbiased opinion of them. And you could use DBman or Links to categorise and rate them! Any of the helpers at GT support forums interested?...
Anyway, to get to the question in hand, I've only tried a few but maybe I've been lucky. The ones I was happy with are Hiway -
www.hiway.com , and Vservers
www.vservers.com , and I never lost any data with either. Hiway are more for beginners, they don't have telnet access or some of the more advanced stuff, but they're pretty good at what they do. My current host is Vservers, who would be aimed more at advanced users, because you have access to your server config files, and you don't want to play with them until you know what you're doing. And again they're pretty good at what they do. They answer questions, they have an excellent (huge) manual and their performance is pretty good too, through two different bandwidth providers. One thing about Vservers though is that although they welcome you running your own apps on the server, they *won't* support anything that's not standard on the server. And they stick to their guns about it too!
So if you're starting out and you don't want to spend too much, Hiway are good. If you're comfortable with Unix and want to go a bit higher-end, I like Vservers (I run on a Vserver Pro - And if you decide to go for Vservers, tell Dave Kaylor the cranky Irishman sent ya

).
Up for non-recommendations are RapidSite, and DSVR in the UK. Sorry guys, but "could try harder"!
Well, there's my two cents.
Kent Brockman
(God, so many smilies! I gotta kick this Perl habit)