http://www.worldwidewords.org/

From JSB: "What is the origin of the phrase to the nines?"

There are at least half a dozen theories about this one. What we do know
is that the phrase is first recorded in the late eighteenth century in poems by
Robert Burns. One very persistent theory is that the British Army's 99th
Regiment of Foot were renowned for their smartness, so much so that the
other regiments based with them at Aldershot were constantly trying to
emulate them - to equal "the nines". The big problem with this theory is that
the story dates from the 1850s, and the phrase is older. Other attempts at
explanation connect it with the nine Muses, or with the mystic number nine,
or even perhaps reaching a standard of nine on a scale of one to ten - not
perfect, but doing very well. Walter Skeat (the editor of the Oxford
Etymological Dictionary and the first secretary of the English Dialect
Society) once proposed that it could originally have been "dressed to the
eyes", which in medieval English would have been "to then eyne"; the
phrase could afterwards have mutated by the same principle that caused "a
norange" to change to "an orange". But the reverse problem of dating
arises here, in that if it were truly medieval in origin one would expect
examples to have turned up before Burns' time. Short answer: nobody
knows.