Hello. Hopefully I can provide some input into this, having come across a similar need for a workaround to this feature/problem and a possible solution (hack)…
In short I wanted store.com/product to always be store.com/category/product no matter where the product is output (sitemap, category, custom modules etc)
However the reason Magento doesn’t adopt this approach is a product can be in multiple categories. It only appends the category path when it is viewing the direct category a product is assigned to.
I wrote a brief article about the reasons behind it, and a work around if people must only have one URL per product.
However the caveat is that if a product is assigned to two categories /store.com/category and store.com/category2 lets say, it’ll use only the first URL category path, even if you are in the category2 page.
To use my approach you’ll need to modify the sererval places Magento outputs product URLs (sitemap etc) and add the AddUrlRewrite function.
You can read more on canonical URLs in Magento here...