One problem with these sorts of services is that when they're working, nothing happens, so if I don't get mails for a week, I don't know if that's because everything's been working or if you've stopped running the service.
There are lots of complex answers, but an easy one is just to have a "last checked" for each URL - it's ok if I have to go on-demand to make sure things are running. (A weekly/monthly update is nice too, just more work.)
Let them enter a url to a script on their own server, that you will POST to, whenever you check their server. The user can log POST's to a text file, DB, etc., so they know that you are actually monitoring them.
When they see that you haven't POSTed to that file for a while, they know you're out of business, and they are unprotected.
On second thought, make it easy on yourself, and use GET. It's not like there's anything confidential about it.
Regarding the weekly/monthly update: this is something I'm averse to. Other services do this and it kind of bugs me each time I get these.