just brew it! wrote:AllGamer appears to give you your own virtual server (i.e. you have full control of it), hosted at their datacenter. I've never used them, so I don't know how good they are.
Another option would be to get a generic virtual server from someone like Linode, and configure a Minecraft server yourself from scratch. I would not recommend this approach unless you're already familiar with administering Linux servers... and it looks like AllGamer may be cheaper anyway.