Soeren found an article on easier deinstallation on O'Reilly. The general idea (for the pointy-haired bosses among you who don't have time to read it) is that every application would get an additional .plist file in its bundle containing the paths of files (like its prefs file) that can be safely deleted along with the application to clean up support files, like the ones in ~/Library/Application Support.
Problems of this approach
My one regular reader may not be surprised to hear that I don't think the paths idea is a robust enough approach. For one, it would break when the user renames a hard disk. Secondly, some support files' paths (e.g. Photoshop's swap files) could be configurable, and then the .plist-info would need to be modified. And it'd be even messier if several users could provide different places to keep these files.
Putting support files in the app bundle itself, as some commenter suggested, has similar problems, especially if the software is on a server and shared between hundreds of users. It'd circumvent users' disk quota and make permissions for an app bundle unnecessarily complex.
My suggestion would be to simply add some sort of metadata to such support files and then use the Spotlight index to get rid of such files. Whether it's done using access control lists, an xattr that simply says: kIsSupportFileOwnedBy = de.zathras.talkingmoose, or they define an OS9-style creator code in your Info.plist that says that all files with this creator are deletable support files, I don't really care.
If all apps were required to give their support files such attributes, one could even have hard disk clean-up apps that can quickly find any orphaned files, like it was possible on Classic MacOS with creator codes (e.g. FileBuddy checked for files with unknown creators and offered to delete them). It should also be supported by NSDocument without too much work ... NSDocument's bad support for creator and typecodes is the main reason for bad creator support, along with an ambiguous policy on Apple's part and the discontinuation of the type/creator registry on their homepage ages ago.
Maybe it should even be a list of owning apps' bundle IDs in an xattr. That would allow extending this to other kinds of files. E.g. a shared Framework could be auto-deleted when all apps that own it have gone.
Of course, Finder should generally ask whether the admin wants to delete all support files for all users who've used this app. After all, they may want to remove the global copy of the app and give two users who still need it local copies when an app is phased out. In that case, they'd want to be able to keep those users' files.
Other installation/uninstallation improvements
While I'm at it, here's an idea for making all applications drop-installable, even when they need an installer/uninstaller: Apple could support install and uninstall executables (which could be any of applications, shell scripts or .pkg files) that reside in an application's bundle in a standardised location:
Users simply copy over the app, and when they first launch it, the Finder runs the installer in it, deploying all needed files. When you delete it, Finder finds the uninstaller and offers to run that.