[rab] With server farms you tend to get what you pay for -- decent reliable dedicated servers run at least a hundred a month in dollars and not very much less in pounds. If you want to pay a lot less than that and want top quality hardware and good service, you might consider a Xen host instead. The decent providers use very good hardware and they maintain it with a lot of care because if it goes down, more customers are affected than just you. And you can't tell the difference in terms of availability and performance; if anything it'll be much better than a cheap colo because most of the time the (often very muscular) CPU is way underutilized. You never get less than the share you're paying for and more often than not you get much more when you need it. And it's spectacularly easy to fail over to another machine -- a good provider will be able to switch you to new hardware in a matter of minutes if smoke starts pouring out of the box you're on. Frankly I'm seriously considering going back to that my self, mainly for that last reason.
Oh, for three years I ran mcios and several other sites, both http and https, an SMTP server, a jabber server with several transports, mysql, pop3 and imap, the homebrew chat server of course and a variety of other services that came and went over the years ... all in 64MB instance of User Mode Linux; a poor man's Xen. It was a little swappy but completely responsive and reliable. It was on good hardware though. A 256M Xen host would be an Aston Martin by comparison.
[Dan] Thanks for that - I was considering a 128MB Xen Vps but was slightly concerned it might not be up to the job of serving this site, which gets something like 5k hits a day.
[rab] How about hosting in Edinburgh? Though you'd probably want to traceroute them to find out if it's really close to you in terms of network hops; I'm three miles but 12 hops and 85ms from mine because of a lack of local peering between carriers, but your situation is likely to be different. Very low latency could be handy for maintenance; you could just mount drives remotely.