I pay $20/mo for a linode at
www.linode.com. I choose what distro gets loaded (Debian for me...) and have full control - root access, create users, etc. When I did some work for Jim C. he got set up on one as well for his stuff (it looked like he'd need the extra disk space and bandwidth instead of riding on mine). I run 2 IPs on the box, so I do my own primary and secondary DNS (a buddy has 3rd level DNS for me as well), I can run mail, imap, pop3, webmail, anything I darn well want. It is the same as having a co-located server, without the $$$$$ and hardware...
Also, I've been upgraded quite a few times over the past 3 years - more RAM, more CPU, more disk, more bandwidth. Only downside is to get more disk or RAM you have to reboot the machine...