I have set up a few clients with Gradwell - they are not the cheapest but the service is excellent. The customers were the sort that I did NOT want coming to me complaining that their email was down! Websites I can deal with, but email is much more important to most people.

1 & 1 are also pretty good - we were looking for a dedicated server on a different IP address from our existing system (for Google purposes, ahem) and have got one of their W2K3 £80/month deals and they are pretty good. A colleague has one of the £60/month systems (Celery processor and less memory) and it also seems good. It is hosted in Germany and is IDE only with no backup service as standard, but you get Terminal Services login and a [censored] (darned) fast connection.

Gareth