My theory on the XML problem was that it was actually a CLR call-out. Tally seems to work well, it shows an up front execution cost that is not comparable to the others, but it seems to perform better.

I'm going to try to tweak each idea a bit and put them under more competition scenarios to see which ones fare better at scale with parallel use.