What you are describing about the RedHat 9/7.2 programs would appear to be their binary RPMs. RPMs compiled for one version would not (for the most part) not work in a different version because binaries would be linked against different libaries. Sometimes (more often than not) when you try to run something using different libraries, it may not even run. If it does run, sometimes it would seg fault.
RPMs for 7.2 may work in 7.3. It really depends on what that RPM is linked against. 7.2 and 7.3 aren't too different, so sometimes you may be able to get away, but like I mentioned earlier, it depends on the libraries linked against.
When you update your X server, you are probably updating your X libraries. Some programs may run, but some may break. Usually X doesn't change too much (more like additions), so you probably don't need to recompile those apps (stuff like Mozilla, Gimp, etc).