When I bought my refurbished T41 from IBM, one of the first things I did was call IBM and request the recovery CDs. They sent them out chop-chop. I would assume Lenovo would do the same.
Drop me a line if they don't and we'll see what we can work out. :-)
Cheers,
Scott.
(Who is sorry you've had trouble with this. Software's still too temperamental.)