Agree with Chad. Fix the plugin code base. But that might not be necessary for this particular issue.

In the meantime, I have a suggestion, which might be a bad one, who knows, but it may at least spark a better idea. I'm against "notifying" users via blog post or even the plugin page itself, because it would mean users would have to stumble across those pages to find out the info. Sure, it would be better than nothing, but it would still leave thousands of users in the dark. The only good place to notify users is within their site's admin - specifically on the plugin admin page. My idea: When a plugin is removed, a fake plugin (generic that is used over and over again) is put in its place. This plugin is designed so that it triggers the "this plugin has an update" notification on all sites using it. The big difference, however, is that when a user attempts to do the upgrade, nothing of the sort happens. Only a message pops up (kind of like how an error message pops up if the plugin directory cannot be connected to). The message can be generic. "Problem with this plugin exists. Check the status board for more info". Then a link to some running list of current plugin problems is shown, where users can discover what's going on. Core shouldn't be deciding whether or not users should deactivate or not. Users should decide that. Core should merely be informing that there is currently a problem, which may or may not affect their site negatively. If it's a temporary problem that is being handled, say so. If it's a permanent problem (like the developer decided to remove it for good), then say so. All on the status board. Ok, that's my idea. Hope it sparks something that can actually be done.