I think the issue with it is the "breadcrumb" format - a breadcrumb, intuitively, is a single path back to where you were. So, multiple breadcrumbs invite confusion!
That said, where you are cross categorising products, it makes sense to let the user know that there are multiple routes in - as it's often impossible to know which would be the best route for them.
So, I would say - keep the single destination and multiple routes, but look at other ways of demonstrating this to your users (and search engines).
To use a very simple example, you might say: "This product is filed under..."
- Delicious shoes
- Orange shoes
- Shoes from shoeland
You also don't need the redundancy of the complete route back to the homepage. If your user has landed on an orange delicious shoe from shoeland, then stick to the choices that are directly related to that. They are there because of one of those characteristics, but you cannot be sure which one - so give them pointers to each. But you don't need a pointer to every possible related category, just the relevant ones.
If that means that a breadcrumb-style navigation element is too simple, then so be it! Just take care when designing any replacements.