Sounds like it maybe a rootkit virus. Could you try using the ultimate boot cd and adding the latest combofix onto the disk and running that? Combofix has saved me formating machines so many times and seems to be great at rootkit removal. ComboFix Download
You could try boot a Linux live cd and installing it, it would replace the MBR with an alternate boot loader so if that installs and boots then you know it's something malicious that was in your MBR. If you cannot install it then that would suggest something more serious, i.e. somehow it's got into BIOS but I wouldn't have thought that is likely, particularly if you can re-flash it with no problems.
It does sound like a hard drive isolated thing, try it with a different drive to make sure. If it still shows up with a different hard drive installed then it may have compromised the firmware, that is a back to factory repair if a BIOS upgrade does not fix it. There are things that can infect the firmware of the keyboard and so even a BIOS upgrade will not cook them but this is unlikely given the lack of error when you boot with no drive.
I would do a low level format of the HD in question and maybe a boot and nuke wipe an see if the problem persists. If it does try booting with the keyboard detached and using a usb keyboard. The other unlikely scenario is that the hard drive firmware has been compromised, if so it may be worth looking for any HD firmware updates that are avalible in order to reflash the HDs firmware.
I have never personally encountered any viruses that have compromised the system that thoroughly but they do exist at least in highly targeted proof of concept attacks.
First of all download MBRCheck from here and run it on the laptop. This will tell you if the MBR has been modified (green = / red = ). To double-check you can also use GMER.
If it is a MBR rootkit (Mebroot, Torpig/Sinowal etc.), all you need to do is simply recreate the MBR via the recovery console or the command prompt on a Windows Vista/7 install disc (see below for the commands to use). Symantec also have a removal tool for Mebroot here which rewrites the MBR.
Just to be sure there aren't any other nasty's lurking on the HDD I would scan it using a bootable anti-virus disc (AntiVir, Kaspersky etc.).
For XP run fixmbr and with Vista/7 run bootrec.exe /fixmbr. With the latter OSs you can also completely rebuild the BCD but this probably isn't necessary...