It's not hard to implement at all. What would be hard is getting the co-operation of plugin developers.
Basically it could work the same way as the RDF in Mozilla Firefox. Every plugin developer would have an file for their plugin which is basically an XML file which at least shows the following information:
- Plugin current version
- Min WordPress version (eg 2.0)
- Max WordPress version (eg 2.1)
Any time the admin panel is accessed, an update check could be run. This grabs all the update files for each plugin and assesses whether they are the same as the existing one or not.
Then the user will be notified that plugin updates are available.
If a user submits their plugins to sites like wp-plugins, then these sites could have their own update file generator, which makes it easier for plugin developers.
This really is simple to do. It just needs co-operation from developers and/or people to code these changes into existing plugins. Ultimately, WordPress could be changed so that it would actively refuse to activate a plugin that didn't have an update file location. This way, new and updated plugins would be forced into compatibility. Strong-armed, perhaps. But it's for the greater good.