BinaryCompatibility is when the past comes back to haunt you.
Application programmers sometimes see it in that they need to load data from files which were written with previous versions of the program, possibly in a less-than-optimal format.
However, the big hit by BinaryCompatibility is when your product is an OperatingSystem or ToolsAndLibraries?, in which case an update to a library must preserve all documented (or undocumented but widely used) behavior of the previous incarnation.
Many methodologies, such as RefactorMercilessly are strictly at odds with BinaryCompatibility.
See also FragileBinaryInterfaceProblem.
This isn't a problem provided you place versioning information at a well-defined place that isn't going to change ever, such as at the start of the stream. Another very good technique is to use XML or XML-like structure so you can add and remove attributes and classes as you want. This makes the application forwards, backwards and laterally compatible. Then, you may RefactorMercilessly all you want.
As for library compatibility, you don't always have to maintain backwards compatibility, especially with static libraries. Just deprecate the old behavior and give clients one or two versions to upgrade. Then mercilessly delete the deprecated features. If clients don't like the changes, they won't upgrade and their code will still work fine. -- SunirShah
Lack of BinaryCompatibility often results from PrematureOptimization. XML is a somewhat unoptimized data structure.
Another possible solution is to TranslateMercilessly?, as in http://www.research.ibm.com/daisy/ . Applying this to libraries is left as an exercise to a PhD student.