Virtual Private Servers Revisited

With Lynn gearing up to move, I need to figure out a new place to host my DNS. Virtual private servers running user-mode linux seem to be a good option. I'll have root, and I'll be able to do anything I want to the machine. This initially would only be running DNS and maybe a mail relay, but I figure for the right price, I could maybe a cram a JBoss and an Apache server in there while I'm at it.

I had originally liked PDXColo, but they're at capacity right now and aren't adding any accounts.

These guys seem to have attractive prices. For $15/month, I could have 128M RAM, 2G of disk, and 20G of bandwidth. JVDS has cheap and tiny machines starting at $12.50. These would not be good for a JBoss server, but their setup prices are cheaper.

Does anyone have any good thoughts on this? See any other packages that look nice? Advice?