Having each package specify the package specific part of the breadcrumb trail as before, but then passing it to the master template for display sounds like the right way to do it to me.
In general, having some agreement about which doc elements the site wide master template is responsible for, and which the package client pages are responsible for, is also an excellent idea.
Sounds like more work for the Clean Up Team! Which I'm happy to pitch in with. Having a solid, consistent core seems more satisfying to me than bolting on another gadget :)
It's no problem to hold off submissions til after the release - that way it's easier to see what direction people want to go with these kinds of decisions.
