Hi Gregster. I feel your pain. Having worked on Magento for the past three years, I've come across a lot of "issues" you'd expect a top-tier e-commerce solution provider to have under control.
I've written about getting canonical URLs in CMS pages here, something that many Magento SEO extensions don't do. I also had a custom SEO extension created and would be happy to share with you. No cost. Just use it.
I don't know if you have multiple languages, but that alone will create an exponential amount of duplicate content from dynamic parameters. Go into your WMT and set those parameters to be ignored. If you aren't sure how to do that, it's well documented here and on Google, Yahoo, and Bing webmaster sites.
I recommend you nofollow the login, search, and cart pages through XML layout. That will cross off another 500 pages or so.
One last mention is that RocketTheme has created a pretty neat extension that will get rid of the p parameter altogether by using JS to switch from grid and list views. Or you could just select in your admin to only allow either grid or list instead of both.
Any more questions just ask.