before I could tell you the best way to get your ranking backup I would have to look at your site.
I Would bet you that because you have bad back links that you try to remove you might've missed a few.
"There are 2 other paid links from two PR4 sites that look editorial. There are other links on the sites to other websites that are paid. All links for these 2 sites look editorial."
Google it is a $40 billion a year company that has the resources and ability to figure out if it's a paid link or looks like a paid link. They will find out from other sites using similar services paid links are one of the worst things you can have in my opinion.
Do a title tag like this is spamming
running shoes | walking shoes | cross-training shoes
using something like Shoes - Walking - Running - Cross-training
would be a better title tag
"Google changes the way the title tag is displayed sometimes in the search engines."
This is normal for Google will change your title tag to suit the queried keywords. It is supposed to help you.
"We may have many 404 errors (due to some mistakes we made with the URLs in our cart) - if Google hasn't deindexed them all then we could have dozens of 404s on important category pages. But nothing is showing up in GWT."
Are you only using Google Webmaster tools to try to figure out if you have for 404's?
when you say blogs I'm assuming your meaning posts?
when you delete blog posts and other parts of the website you're essentially deleting interlinking, back links that you may not know about, your changing your website structure.
If you have not corrected all possible 404's or at least most this will hurt you quite a bit.
For instance when people redesign their site and do not 301 redirect properly even sometimes when they do 301 redirect properly they go down drastically in the SERPS
this is because Google does not trust change immediately.
if you scroll down you'll see my answer in this post and its relevancy to changing parts of the website and Actually trying to keep your site rank.
http://moz.com/community/q/how-to-keep-old-url-juice-during-site-switch
" We have a lot of subcategory pages that rel=cononical to main categories in the menu."
That might not be the wisest idea.
I would strongly recommend a site audit.
if you give me your URL I will run it through some tools for you and give you my opinion.
Sincerely,
Thomas