I never heard that term before. but

"brand spanking new"

is very common.

Must be related?

I, too, have grown-up with the terms:
"Brand spanking new" and "Spick and Span" (commercialized in the US into a cleaning product; Spic-n-Span)

Span-new is new to me, but brand spanking new, I have heard all my life.

There is an excellent description of the origin of the phrase at http://bit.ly/span-new.

I've never heard of span-new either. It'd be interesting to get a world-view on this one; with our assortment of members, it is possible.

Brand new and brand-spaking new I have heard.

Speaking of which, where does 'brand new' come from?

These are Anu's words about it in today's compendium:

"The term "brand new" refers to a brand (a burning piece of wood), implying straight from the fire, i.e. newly made in a furnace. Then there is "brand spanking new". The word spanking here is as an intensifier, used in the adverbial sense of the word, meaning extremely or remarkably. There appears not to be a connection to the spanking of a newly born baby to gets her breathing started.
The spelling spic-and-span and its association with cleanness is from the popular household cleaning product Spic and Span."
-Anu Garg

And where does the "spic" in the spic and span, come from??

hmm.. from Spiculispongiae ?

Spic`u*li*spon"gi*[ae]\, n. pl. [NL.] (Zo["o]l.) A division of sponges including those which have independent siliceous spicules.

that gets my vote.

Why not? Sponges were used to scrub floors with Spic-and-Span when it was concocted.
In fact I still use one, tho' it is often on the end of a stick.

Such an educated guess. I love your joy and humor.

Stick and Span.

Imagine
stick-span-spic? spic-and-span-and stick? or spic,stick and span?
None of those work, your's is better.