Hmmm, just checked Canada Post's website, and came across lithium batteries under the list of dangerous goods that are non-mailable:
http://www.canadapost.ca/tools/pg/manual/PGnonmail-e.asp
"Class 4 – Flammable Solids, Spontaneously Combustible, Dangerous When Wet
calcium; cellulose products; fire starters; fuel tablets;
lithium batteries (excludes lithium-ion battery); magnesium; matches; moth balls; naphthalene; nitro-oily cotton waste; oil impregnated fabrics; phosphorous; sodium"
Interesting .. so they ban lithium batteries because of the flammable risk of lithium metal, but allow the composition of Li-ion to pass.
Oh, and this tidbit from their General Terms and Agreement:
"6.3 Canada Post shall not be responsible for meeting any service standard or delivery commitment, where applicable, for delays arising from the mailing of non-compliant Items."
So, I guess I can assume there is little hope of those 80 pcs titanium batteries ever showing up. I guess my previous pure battery orders were of small enough size not to trigger the customs evaluation (i.e. under $20, there's no fee). All the other ones I can think of had flashlights included, so I guess the custom tag didn't specify the batteries (would have sucked to have lost my surefire L2 over this - I bought 10 batteries with it). Glad that order showed up!