Sounds interesting. On the other hand, maybe we could do it manually (from a packager's point of view) : if you package library foo, and you know that version 0.1 is not supported anymore (noone knows that better than you since you maintain it), you can add an Obsoletes tag to your libfoo5 package, and force the removal. Would that solve Jeff's issue ?
Or you release a new release of that version which provides the garbage collector symbol, Axel suggested.