I have used sevaa for a while now and have nothing but great things to say about them.

Oh, and they have mod_perl. Prices start at $2.50 per month (that is the plan I use for my personal site).