If it won't even work with the recovery CD and refuses to format the hard drive and start again, it sounds like something on the hard drive has got seriously corrupted. It certainly sounds like either a RAM or hard drive issue but I'd say that the way the problem was caused suggests it's more likely to be the hard drive. Assuming you have already either backed up anything you want to save on there, I'd try booting into DOS and using FDISK to format your drive through there, rather than let the OS do it. If there's a corrupted version of the OS on your hard drive which is causing issues during recovery, the logical thing to do is totally wipe the partition and start again with the hard drive. Once you have it wiped and then the primary partition re-created and blank, try using your recovery CD again.
If your laptop has a floppy disk drive, create a boot disk for DOS on another computer (I normally use the Windows ME emergency startup disk even though I run XP, any will do really) or alternatively download a DOS bootable CD such as UltimateBootCD and run that. You will need to enter your BIOS on start up and change your settings so that the first boot device is your CD drive or floppy drive, whichever is appropriate.