Unfortunately, what Google can do and what they actually do can really vary. If you're mixing signals and doubling up the canonicals, the odds that they'll get it right are pretty low, in my experience. I think it's worth the fix, if these are traffic-generating pages.

Yeah, I'm honestly not 100% sure on the HTTP header version, but I'd bet they don't support it. It won't hurt to try it, though, and you'd at least cover Google - I think it's probably a good best practice for PDFs that have HTML equivalents.

Definitely some turbulence at the end of July, and around Panda 3.9. If you haven't seen it, keep an eye on our new project, MozCast:

http://mozcast.com/

I don't believe that Bing supports the HTTP header version of rel="canonical". They do technically support the link attribute (their comment about it being a "hint" was from 2009) - Duane confirmed that last year (I asked him point blank). Although, honestly, experiences vary and many SEOs claim that their support is inconsistent even for the link attribute.

Honestly, when it comes to canonicalization, when in doubt, try it. The worst that can happen in most scenarios (implemented properly) is that it just doesn't work.

Out of curiosity, why are your trying to use the HTTP Header version. Is it a non-HTML file (like a PDF)?

Yeah, wish I could give you a simpler answer, but I'm afraid it might end up being a little tricky. Hit the biggest problems first, and at least you can manage time/money a bit. The one bright side is that the rules should be no harder to code in ColdFusion than anything else (PHP, ASP, whatever). It's just the core logic that's tricky.

Unfortunately, the rules may differ from page to page and will be entirely dependent on how your pages are generated. If it's just a matter of the "index.cfm" version vs. root ("/") versions of pages, those canonical should be straightforward. For the other parameters, though (like "i", "fs", etc.), it depends entirely on the function of those parameters.

I know ColdFusion reasonably well, and even given that, I couldn't give you a one-size-fits-all rule that would solve the problem. It really has to be guided by your site structure and code/data logic. Personally, I'd start with the pattern that generates the most problems and solve that one first. In other words, if one template (like "/press-releases") generates dozens or hundreds of duplicates, deal with that first. If you solve the top 3-4 problems, you may clean up quite a bit. That could be more effective than trying to fix everything at once.

Seems like you got the 301-redirect resolved below - if you've got that in place and fixed the canonical tag, it should be ok. It'll just take some time (usually longer than you'd like) for Google to clear out the pages, especially the deeper ones. If you see gradual de-indexation, though, you'll probably be fine.

Could you provide an approximate example that matches your real situation (a fake domain is fine, but with the same basic format)? This is a situation where fake examples that don't match the real situation probably won't help us (or you) much.

Once you have the spreadsheet, how are you going to translate that into tags? If this is a dynamic site, it would be better to be able to code rules to set the canonicals - and potentially much easier.

Could you clarify a couple of things:

(1) When you say canonical URLs, do you mean your internal links, or the actual URLs in your rel="canonical" tags?

(2) If it was just the canonical tags, is everything consistent now (tags, internal links, etc.)?

Since both version will resolve, just fixing the canonical tags (if that's the issue) should be enough - it's just going to take a little time. They should be as effective as a 301-redirect in this case. Either way, though, it can take Google a while to kick out the duplicates. I'd just monitor the index closely and make sure the top-level pages are clearing up (i.e. your home-page and major category duplicates should be disappearing). If that's happening, you're ok - you just need to wait a bit. If that's not happening, then you may have some other mixed signals in play.