The story
Uncertain. Perhaps a variant of spander-new, or from spick-and-span, both attested from the 17th century, while spandy clean appears in 1838 (see quotations below). Both spander-new and spick-and-span come from earlier span-new, which is attested from c. 1300.
Etymology from Wiktionary, CC BY-SA 4.0.