I'm working with IntoVPS. Never had any problems with the service and it is well above average for the goodies they offer.

If you opt for a shared hosting solution, I use Dreamhost and I can install any Perl modules into my home directory, even compile C and XS.