Since the introduction of WooCommerce, I've been looking for any easy way to keep a consistent permalink structure for my clients. They all want store/category/subcategory/product in a nice, clean format that progressively builds as you click through the site. They don't want to see the URL structure change... just more added to it.
I've never seen anyone post an easy solution to this so I thought I'd share what I came up with tonight. This plugin is they key to clean URLs:
Custom Permalinks by the developer of audiobus. Look him up.
You can't just activate it and be happy, there's a little more work to do (not too much). Here's the structure I've been trying to enable for months:
To achieve this, I created a page called products and set the shop base page to the products page -- WooCommerce > Settings > Pages. I then went to the WordPress permalinks settings and changed the products category base to "products" -- Settings > Permalinks. Also also changed the product permalink base to default.
After getting that set up, my product categories work exactly as they should each click adds the next portion of the URL, products/category/subcategory/
All I have to do to tack the product on the end of that string by using the custom permalink field for each product. Each product will default to a non-pretty permalink so your only responsibility is to manually make it pretty. Add your custom hierarchy to each product and make everything awesome.
Disclaimer: I realize that WooCommerce hasn't added this functionality because it can supposedly cause conflicts (read this). I've tested this strategy on WordPress 3.5.1 and WooCommerce 2.0.8. I have not tested this on older versions of WP or WC. Your mileage may vary. Just try to be sure that you aren't using a base URL structure that could conflict with the default wordpress configuration.