The partition table is part of the MBR, but the MBR also contains the master boot loader code. Reformatting only overwrites filesystem structures within a partition, and repartitioning only overwrites data in the partition table portion of the MBR. Although you might expect the Windows installer to also overwrite the boot loader code, it probably doesn't, for compatibility reasons. On multi-OS systems, for instance, it's entirely possible that your MBR contains stage 1 of the GRUB/GRUB2 boot loader, and that you don't
want Windows to overwrite it with the (less capable) Microsoft boot loader.
In fact, I should have thought about that before I linked MBRCheck. I hope your laptop wasn't dual-booting Linux or something. If so, you may have just blown away a perfectly good GRUB. I'm not sure if MBRCheck is aware of GRUB, LILO, etc. :/
Otherwise, it sounds like you did have boot-sector root kit. The most likely culprit is something in the TDSS/Alureon family. It is usually not possible to remove these with conventional AV programs due to the fact that the (malicious) boot loader is executed before the processor even switches to protected mode, let alone before the kernel is loaded. Basically, your entire OS and everything running within it is "inside the matrix" from the moment it's "born".
Kaspersky does make a free tool that specifically targets the TDSS/Alureon rootkit family. With a working knowledge of exactly how these rootkits work, it is theoretically possible to remove them from within the infected system.
TDSSKiller (download on
this page)
I've had mixed results with it in the past, but hopefully if you can get the MBR portion cleaned up first, it will be able to finish the job. The MBR code is only part of the rootkit. This rootkit family likes to infect low-level disk-access drivers like ATAPI.SYS, and if you don't clean that portion as well, 1) You'll still be root-kitted and 2) they can re-infect the MBR.