[evanwalsh]

If you're comfortable getting dirty, I'd check out http://prgmr.com/xen/

[pmb]

Thanks! This looks ideal for my needs!

[wensheng]

I have a small one from them as a NS server and has no issue at all. However their bandwidth allocation (40G for 256m plan) is not enough for pretty much anything else.

[dholowiski]

I have two small servers from them. Highly recommended (if you don't mind getting your hands dirty).