#Ruby: 50 46 characters (1020 characters output)
s="";999.downto(0){|i|s[n=i.to_s]||s+=n};$><<s
Sample run:
bash-4.1$ ruby -e 's="";999.downto(0){|i|s[n=i.to_s]||s+=n};$><<s'
999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100
Test run:
bash-4.1$ ruby -e 's="";999.downto(0){|i|s[n=i.to_s]||s+=n};$><<s' | ruby -ne 'p (0..999).reject{|i|$_[i.to_s]}'
[]
##Ruby: 113 characters (1017 characters output)
s=[*0..999]*"";0.upto(999){|i|s.gsub(Regexp.new i.to_s){break s=$`+$'if[*0..999].all?{|j|($`+$')[j.to_s]}}};$><<s
Sample run:
bash-4.1$ ruby -e 's=[*0..999]*"";0.upto(999){|i|s.gsub(Regexp.new i.to_s){break s=$`+$'"'"'if[*0..999].all?{|j|($`+$'"'"')[j.to_s]}}};$><<s'
100110111200201210211220221222300301302310311312320321322330331332333400401402403410411412413420421422423430431432433440441442443444500501502503504510511512513514520521522523524530531532533534540541542543544550551552553554555600601602603604605610611612613614615620621622623624625630631632633634635640641642643644645650651652653654655660661662663664665666700701702703704705706710711712713714715716720721722723724725726730731732733734735736740741742743744745746750751752753754755756760761762763764765766770771772773774775776777800801802803804805806807810811812813814815816817820821822823824825826827830831832833834835836837840841842843844845846847850851852853854855856857860861862863864865866867870871872873874875876877880881882883884885886887888900901902903904905906907908910911912913914915916917918920921922923924925926927928930931932933934935936937938940941942943944945946947948950951952953954955956957958960961962963964965966967968970971972973974975976977978980981982983984985986987988990991992993994995996997998999
Test run:
bash-4.1$ ruby -e 's=[*0..999]*"";0.upto(999){|i|s.gsub(Regexp.new i.to_s){break s=$`+$'"'"'if[*0..999].all?{|j|($`+$'"'"')[j.to_s]}}};$><<s' | ruby -ne 'p (0..999).reject{|i|$_[i.to_s]}'
[]
Combining the above two solutions results 139 characters of code which produces 1008 characters of output.