MyPackage.deb depends on GTK 2.19, because it is based on functionality that was deprecated in 2.20. What happens when when I want to
apt-get install TheirProgram or
dpkg -i TheirProgram.deb and GTK 2.21+ is a required dependency? What should I do in situations such as these?
Generally speaking, new versions of libraries which introduce backwards incompatibilities should change their soname, and this will then result in a new package name for the runtime library (e.g. for GTK+,
libgtk2.1-0 or whatever is appropriate). It's usually considered a serious bug to introduce a breaking version upgrade without following this rule.
This means that, in most cases, both runtime libraries can be installed simultaneously, and dependent packages too: your
MyPackage.deb would pull in the old library,
TheirProgram.deb would pull in the new one. This is used in Debian during library transitions: when a new, backwards-incompatible version of a library is uploaded, a transition is started, and until all the dependent packages have been rebuilt, both versions of the library are available in the archive.
Of course as a general rule distributions try to only carry a single version of a library at a time, so the old library will disappear from the archives, but as long as you've got it installed,
MyPackage should continue to work. You won't get any security support on the old version of the library though, and there are no guarantees that it will keep on working (or that no other package will break it), so for the long term you'd be better of fixing
MyPackage so it works with newer versions of GTK+.
If the new version of GTK+ is backwards-compatible, then the package name won't change, but (bugs excepted) the runtime library will still allow
MyPackage to work — so installing
TheirProgram will force the GTK+ upgrade, but
MyPackage shouldn't be affected. (It might print more deprecation warnings during execution.)