Well Minaev, I had about the same error, some months ago.
I had the service partition unaccessable.
The only difference is that although i my country, Romania, the reluctancy is towards selling the recovery sets, not towards ordering and using them...they ordered a set for my laptop. And later made me a copy, since I was still warranted in some countries. Still I had to pay for that, too (Grey-zone service).
So gladly I rewrote the service partition with the recovery cd's...everything went smooth and l o o n g until the recovery procedure...it went about until 35% and then said, the system cannot be recovered, although it installed someting of the OS.
After that it neither booted, but entered into the recovery console.
So I realized that it should instead boot into the partition that had windows installed, and tried the recovery repair diskette, an ISO actually on a bootable CD, and after several attempts, with the various options (the 3.1 or 3.3 version of the diskette, NOT the 4.0-which is of little help under previous WinXP installations), the system booted into Windows and a DOS-like installer took over the machine and continued a OS installation, and finally booted a clean, fresh copy of its legitimate GUI Operated environment. Except the fact that IR did not work all the time, and there were some USB flash disks that it did not recognize.
(after that I went and made recovery disks very obedient and hoped never to have to use them)
Otherwise it went smooth. That time.
A second time I tried to do that, namely last friday on 30th of march, I went through the installer and stopped, upon reboot it entered the recovery console. I suspected that the recovery partition was still there and active...
I had ready an utility to view (Acronis Partition Expert Boot CD) which was active. Set the Windows partition to active, it tried again to reinstall the OS as last time, as above, it tried to boot, then said the gracious message
<Systemroot>Windows/system32/hal.dll - the file is missing or corrupt.
Hoping that the system was honest, I copied it from a desktop on a USB Stick, booted from a live CD, checked and stupor, hal.dll, was nicely fellowshipping with the others in the system. I compared with the filed i took from the desktop, and the seemed identical, but anyways, let us listen to the OS, and I copied the file, a "working" one. Same error upon boot.
After great attempts to lose my temper I still kept it

.
Then I turned my attention to the recovery disks that I made. It took me about 12 hours to try to recover and to discover that they did not work, and the second recovery attempt with my cd's more than 8 hours (overnight).In the end stated 100% of the recovery process but didn't do anything for about 3 or 4 hours. When I rebooted the operating system was missing, or again the precious hal.dll or the partition with the OS was inactive.
Possible solutions:
1.
So I bequeath this attempt to the great IBM service...sometime later. Just to see if they can make it, since I have copies of their cd's. I think that you can send your notebook to the local IBM service and ask them to restore it to factory settings. In Romania it costs about 50Euros to do that, and a great warranty that you're not pirating any OS is to have that service partition still on the HDD.
That was my case. I am seriously considering coughing up the money so they restore it...until then I use another license on my computer since the one it has is transcendent
2.
Untill now I was reluctant to cash out for something I should normally be able to do...I had a friend from the US purchase original recovery CD's from Lenovo, I want to see if it fares any better, when he arrives, in april.
Hope You can manage it. Cheers.