Another issue, perhaps one of the biggest, is that there are no standard mechanisms for naming packages. Because of that, an RPM designed for one system will know dependancies by different names to that of another. The difference between package "python-dev" and "python-devel" may be small, but it's enough to break compatability.
Finally, you have differences in the compiled binaries themselves. A KDE application compiled for Redhat 7.3 will not install on Redhat 8 as they use different versions of gcc, and the binaries produced by these compilers are not compatible. RPM has no way of dealing with this other than to force people to have 2 different packages for the 2 different versions.
A bit of a mess isn't it? If you're a Windows or Mac user you're probably feeling a bit smug right now, but actually there's no reason to be. Windows and MacOS both have ways of dealing with these issues, and neither of them are particularly elegant. On Windows, we are all familiar with the name InstallShield. The standard mechanism for installing software onto Windows has for many years been to create an installer executable that the user runs and then extracts the program from itself and performs any needed setup. The installer checks dependancies (usually different versions of MS dlls) and often contains copies of them just in case they aren't present. Finally it integrates the program with the environment (often too well!) by creating menu entries, app associations and so on.
Why does this system suck? Well, from the point of view of the user, it doesn't, the experience is simple, fast and effective. Behind the scenes however, things are rather ugly. For starters, modern installers are complex beasts - InstallShield is actually a complete scripting language and all the code necessary to interpret these scripts, create the user front ends etc are shipped with the Windows app in every single case. This is pretty wasteful, and the need to ship all the DLLs an app might require just in case they are not present on the system also adds a lot of overhead.
Installer executables bring with them their own set of problems. The user interface is often inconsistent, and they are extremely hard to automate. I once spent a week at a company in which all I did was travel to every computer and put in the IE6 upgrade CD for each one. There was almost no good way of transparently deploying applications. Although products do exist that automate this on Windows, they usually work by watching what the installer does then "rebuilding" the installation from scratch which can lead to all kinds of nasty issues. The current system was never really designed as such, in the absence of any solution provided by Microsoft companies sprung up to fill the gap. Windows is now moving to an appfolders style system whereby dependancies can be sideloaded in an attempt to avoid dependancies also.
Does the Mac fare any better? Unfortunately not. MacOS X has (in theory) totally eschewed installers in favour of App Folders, which are specially marked directories, the idea being that you simply drag and drop the app into the Applications directory. To uninstall, just drag it to the wastebasket. This is good UI, but bad everything else. By eliminating (un)install logic, it becomes extremely hard to check for dependancies, to provide system components, to clean up configuration changes, other application metadata and so on. Although technically apps can have dependancies via bundles, the lack of OS side install logic means that in practice it's not possible to install these bundles into the OS if required - the user must do it for the app. As such, apps can only rely on funtionality that was known to ship with the operating system. That suits Apples goal of selling more copies of OS X, but is rather limiting for the user. By trying to hide the problems dependancies pose all together, it creates bigger problems further down the line. As such, some Mac apps ship with install apps anyway which rather defeats the point. Note that my beef with appfolders are more to do with the way they have been implemented in NeXTStep - you can use autopackage to install apps into an appfolders style arrangement (for instance i test with /apps/packagename) and one day there may well be a VFS plugin that lets you view installed packages as folders/directories. I think it is highly unlikely that you'll ever be able to just drag app directories off a CD onto the system however.
- "Autopackage, Part I"
- "Autopackage, Part II"
- "Autopackage, Part III"



