I've discovered unixshell.com. They provide really cheap linux server hosting. You get root access on a virtual dedicated server, and you can pretty much choose how much memory you want it to have. It might seems little, but most (good) server software doesn't use much memory. That's for the desktop GUI style software. For email and DNS server software I can strongly recommend qmail and djbdns.
I've also figured out how they keep the prices so low. It's unmanaged hosting, meaning that you do all the setup and configuration yourself, and they don't pay some techie to watch you in case you make mistakes. If you screw up you're pretty much on your own, but if you're a Linux savvy user, this might be exactly what you want. With the ssh-to-console feature, it is like having direct access to the server.
I've had a server running at unixshell for a while now, and so far I'm really pleased with the cost and value of their products. With all my usage, I've spent 0.057 of my 128GB per month transfer allowance. Let me know if you find anything cheaper, please.