Seo Rewrite Of Products In Secondary Categories

Hi,

We have recently upgraded our store from 4.1.4 to 4.4.2,
And we have come across a major issue affecting our SEO.

We have a product and its main URL is...
https://www.domain.com/main-category/product.html

The item is also in other categories so appears in...
https://www.domain.com/other-category1/sub-category/product.html

https://www.domain.com/other-category2/product.html

However the "other" categories now report a 404

We have written an addon to redirect the secondary URLs to the main URL, but as the secondary URL isn't working to begin with it wont redirect. We've disabled our addon to rule it out as being the issue.

Any idea why the secondary URLs wont show the product anymore?

Stephen