Backup everything first and then try sort the thing out for him. Why restore CD does not work? If cd key lost, you can find it out by run a small program on his machine providing the machine working. (Have you tried safe mode?, normally press F8 when boot up.)
As he still got MsWinME licence, you can install from your own OS disk if you happen to have one. Of course, you need to use his licence key.
By the way, why have you deleted all restore points. You would have a easy job if you have not done that.