We've been using Dot-com Monitor (
http://www.dotcom-monitor.com/) for the past few months. It seems to work great and I believe it meets all the requirements you mention.
You give it up to three people's phone numbers (as well as email addresses), and if your site is down for more than 15 minutes (or a time interval you set), it gives them a call. They monitor from about 5 locations worldwide. It can also monitor payment processing as well as regular pages. It also gives you the response time it took to load the pages, each time it checks the pages (in our case, every 10 minutes).
Hope this helps.