#Haskell, 156 bytes
import Data.List
a@(r,x)%y|r==['0'..'9']=a|0<1=(\t->(nub$sort$r++t,x++(y\\t)))$[t|t<-tails x,isPrefixOf t y]!!0
g n=snd$foldl(%)("","")$map show[n,n-1..1]
adding in the recycling-checking cost a lot of characters... sigh
example output:
*Main> h 110
"110910810710610510410310210100998979695949392919089887868584838281807978776757473727170696867665646362616059585756554535251504948474645443424140393837363534332313029282726252423221"