You could really run Asterix on any server, be it VPS or Dedicated. I would have to recommend slicehost for the mere fact that you got a Xen solution. I'm not sure about Lylix, as I have never tried them.

Give slicehost a try, unless you find another Xen provider with a different type of offering.