Magento Breadcrumbs are a bit to be desired, when it comes to consistency and SEO purposes. Product breadcrumbs would shift to whatever the latest category they were added to. So if a product goes on sale in a special “sale” category, then the breadcrumb would be rebuilt and shown on the product page.
This had a negative effect on SEO, in that the products where showing up in sales or even newsletter categories.
We found a post here at StackOverflow and an answer by “Fiasco Labs” got us started on the right path.