Op gennem 1990'erne vandt Lehmann flere tyske mesterskaber, og i 1994 var han med til at blive verdensmester i holdforfølgelsesløb.<ref name=cs /> Han var dog ikke med ved [[Sommer-OL 1996|OL 1996]], hvor det tyske forbund satsede på andre ryttere. Efter udskiftning af landstræneren kom han tilbage på landsholdet, og han var i 1999 med til at blive verdensmester i holdforfølgelsesløb igen.<ref name=cs /> Ved [[Sommer-OL 2000|OL 2000]] i Sydney deltog han igen i forfølgelsesløb for hold og individuelt. Han var blandt favoritterne individuelt sammen med landsmanden [[Robert Bartko]], der var verdensmester fra 1999, briten [[Rob Hayles]] samt hjemmebanefavoritten [[Bradley McGee]]. Det var da også netop disse fire, der kørte hurtigst i kvalifikationsrunden med Bartko som bedste med ny olympisk rekord. I semifinalerne besejrede Lehmann Hayles, mens Bartko vandt over McGee. I finalen førte Lehmann i begyndelsen, men omkring halvvejs tog Bartko over og vandt komfortabelt, idet han forbedrede sin olympiske rekord igen. Lehmann fik dermed sølv, mens McGee vandt bronze.<ref>{{kilde | url = http://www.olympedia.org/results/154961 | titel = Individual Pursuit, 4,000 metres, Men | udgiver = olympedia.org | hentet = {{dato|22-4-2022}} }}</ref> I holdløbet kørte Lehmann sammen med Guido Fulst, [[Daniel Becke]] og [[Olaf Pollack]] i kvalifikationsrunden, hvor de klarede sig videre til kvartfinalen på en fjerdeplads, mens briterne var bedst og satte olympisk rekord. I kvartfinalen erstattede Bartko Pollack, og her forbedrede tyskerne den olympiske rekord med mere end to sekunder i sejren over Australien. I semifinalen satte Ukraine ny verdensrekord i dysten mod Storbritannien, mens tyskerne med samme hold som i semifinalen sejrede sikkert over Frankrig. Finalen blev ikke rigtig spændende, idet ukrainerne ikke kunne leve op til deres tid i semifinalen, og da Fulst, Bartko, Becke og Lehmann samtidig brød fireminutters grænsen og satte ny verdensrekord med 3.59,710 minutter, næsten fem minutter foran Ukraine, blev det til sikkert tysk guld og ukrainsk sølv, mens Storbritannien sikrede sig bronzen.<ref>{{kilde | url = http://www.olympedia.org/results/154969 | titel = Team Pursuit, 4,000 metres, Men | udgiver = olympedia.org | hentet = {{dato|22-4-2022}} }}</ref>
Levende_personer