##GolfScript (35 chars)
1000,100>{10base[{.(+}2*]$0=}%.&$0.
Output is
00100200300400500600700800901101201301401501601701801902102202302402502602702802903103203303403503603703803904104204304404504604704804905105205305405505605705805906106206306406506606706806907107207307407507607707807908108208308408508608708808909109209309409509609709809911111211311411511611711811912212312412512612712812913213313413513613713813914214314414514614714814915215315415515615715815916216316416516616716816917217317417517617717817918218318418518618718818919219319419519619719819922222322422522622722822923323423523623723823924324424524624724824925325425525625725825926326426526626726826927327427527627727827928328428528628728828929329429529629729829933333433533633733833934434534634734834935435535635735835936436536636736836937437537637737837938438538638738838939439539639739839944444544644744844945545645745845946546646746846947547647747847948548648748848949549649749849955555655755855956656756856957657757857958658758858959659759859966666766866967767867968768868969769869977777877978878979879988888989999900
(1019 chars) This is a variant on the Lyndon word concatenation approach: rather than use the primitive 1-char words it uses multiples of 111 for shorter code but repeated occurrences of those numbers.
1000,100>{.111%!{111/}*10base[{.(+}2*]$0=}%.&$[]*2>0.
at 53 chars generates an optimal string, which is of length 999 chars:
100200300400500600700800901101201301401501601701801902102202302402502602702802903103203303403503603703803904104204304404504604704804905105205305405505605705805906106206306406506606706806907107207307407507607707807908108208308408508608708808909109209309409509609709809911121131141151161171181191221231241251261271281291321331341351361371381391421431441451461471481491521531541551561571581591621631641651661671681691721731741751761771781791821831841851861871881891921931941951961971981992223224225226227228229233234235236237238239243244245246247248249253254255256257258259263264265266267268269273274275276277278279283284285286287288289293294295296297298299333433533633733833934434534634734834935435535635735835936436536636736836937437537637737837938438538638738838939439539639739839944454464474484494554564574584594654664674684694754764774784794854864874884894954964974984995556557558559566567568569576577578579586587588589596597598599666766866967767867968768868969769869977787797887897987998889899900