In our case, it was more that there were multiple things we could monitor for that potentially indicated a problem with a service but it was hard, using Nagios or whatever, to tie those individual indicators back to a single service going haywire at 3am, especially if all 50 of them blow up at once.
We don't have the precise problem that you describe though - for us the ability to monitor the number of data series in a graphite collection (so that if a server disappears we can notify, and then if another drops off we can alert) is sufficient. Cabot can use this and the ability to tolerate a number of failures to give behaviour very close to what you talk about. However I don't know if Cabot would support the kinds of checks that you're carrying out out-of-the-box, you'd probably have to extend.