We we're in a very similar situation, after much research we did the following:
- Removed or diluted anchor text with diversity in mind
- 301'd into a subfolder to change the URL structure
- Balanced out the ratio of home:interior inbound links
- Purchased and 301'd a number of old relevant domains with decent inbound links
- Added the "cart" to every page as it was previously modified to only show if something is in the basket
- Purchased a range of product specific EMD's for use as buffer sites
And thats where we're currently up to. We're almost back to pre-penguin rankings and traffic, phew!
Dark, we've done a few things and we're getting success in return. However, like everyone else, we've been scrambling and trying all sorts of things at the same time. This makes it hard to isolate our results. Could you rank your list in order of what you felt made the largest difference?