There's certainly room for improvement - but even moving from Windows Update to Microsoft Update took them a while, and that was just a case of extending support to another of their own products! I never cease to be amazed by just how resource-intensive the update check is, either: check for updates on a machine with "only" half a gigabyte of RAM and be prepared for many minutes of disk thrashing as the process responsible blasts through the hundred Mb barrier; at one point last year, I tried a little race, Debian 'apt-get update/apt-get dist-upgrade' against MS Update. In the time it took the Microsoft offering to download and display the list of applicable updates, apt-get had checked and updated not one but three separate machines, all less powerful than the Windows machine - even though the Debian tool covered every application installed.
I'm not sure the current Microsoft Update could realistically be extended much further - it struggles badly enough under the current limited workload. I agree about the InstallShield abomination, too: my heart sinks whenever I find myself having to install and support an application which has been mangled that way.
Rather than extend the existing MS system, though, I think the best route might be an open third-party update mechanism, preferably with central administration facilities and policy support. Having helped support labs totalling a few hundred PCs in the past, I'd love to be able to see that Firefox, Thunderbird, AutoCAD and Virusscan are all patched up to date, or indeed to be told that those three PCs in the corner are behind on patches and need investigation. As it stands, half our applications will tell users (who don't have the necessary account privileges to update anything) that they need updating, irritating users and making us look out of date - the other half silenty wait for an admin user to run them, which may not happen for weeks.
Sure, I could try to shoe-horn every application into some third-party application management setup - but that's a whole new world of pain, expense and overhead. Why can't I just approve and install Firefox, then have a privileged service automatically update to new versions without needing local intervention? I can't go round 200 machines, logging on locally just to update the web browser every other week!