All I did was confirm your code is essentially the same on my SQL2005/1Gig ram 2.8 machine.

My first guess was because you were using a @table variable for your Tally table, I've always heard that @table vars were good only when they had fewer rows.

I ran your code, then substituted my permenant tally table...identical results. second pass saved a few milliseconds due to caching I assume.

/*

Start tally solution

Milliseconds: 3733 | Lines: 25987

Start cursor solution

Milliseconds: 2140 | Lines: 26922

second pass:

Start tally solution

Milliseconds: 3703 | Lines: 25987

Start cursor solution

Milliseconds: 1983 | Lines: 26922

*/

I've just got to assume that although a Tally table is awesome, there will be situations where it does not perform as well as other methods.