merlyn wrote an article about doing this recently in some magazine or other. I don't remember which, but the basic gist was to use Test::More and then use WWW::Mechanize or LWP to check the content. That might be helpful to you. It might have been Linux Journal, if you're interested.

As far as hosts, I highly recommend Bytemark. They provide all kinds of crazy features, including a watchdog that will send you e-mail or SMS messages if your server goes down or a page can no longer be retrieved. It's fairly customizable, too. The tricky part is that you have to set everything up yourself - Apache, mail, etc. But you get root access to your own server. You should at least check it out. Oh, by the way, if they ask for a referrer, use "milkbone". :D