As you know (because you've taken the time to write this plugin!), editing flows are pretty idiosyncratic depending on your organization. In my case, we have contributors who need to be notified only when their story goes live; but we have editors who need to be notified that something has changed from one particular status to another, signifying that they need to log in to WordPress and edit the stuff. I suspect they'd rather not know whenever the status changes to something that doesn't require their action, although I suppose they could just filter those e-mails out or something.
Example of our workflow- (which now use the initial version of Edit Flow custom statuses)-
Contributor submits a post, it becomes Pending Review (which Editor A needs to know about)
Editor A edits the post, it becomes Final Review Needed (which Editor B needs to know about)
Editor B edits the post, it becomes Ready to Publish (which Editor C needs to know about)
Editor C publishes the post, which the Contributor needs to know about.
in short… we have a rather long editing train, and people who are too busy to log in and check WordPress queues, so e-mail notifications become important. So, I don't know how that addresses your question about what granularity is required. I was curious about how you approached the notification issue because I know WordPress doesn't have hooks for these custom statuses, right? (just a hook for any status change…)