Make sure that do all drives formatted and then re-install the windows.However,It is definitely possible for a slightly sophisticated attacker to leave malware outside the direct reach of the operating system. Reinstalling the operating system means a disk wipe at most. Even there, you need to be careful if you restore any data that may have been compromised.
Malware can be stored in one of the many rewritable memories that lurk in just about every component of a modern computer. These memories store that component's firmware and are usually rewritable; all it takes is knowing the right address to it, and manufacturers usually provide tools to upgrade the firmware, so all the attacker to do is substitute his own code (there is almost never any cryptography).
For example, there is a known (and fairly simple) exploit for Apple keyboards, found by K. Chen. Chen's presentation shows how to take advantage of the available memory (only about 1kB to spare) to open a shell on a TCP port by injecting keystrokes, or log keystrokes in a context where a passphrase is expected and replay them.
For another example of a firmware vulnerability in the wild, try CVE-2010-0104: Broadcom NetXtreme management firmware ASF buffer overflow. This is a bug in some Ethernet firmware that allows a remote attacker to take control of the network firmware (and so at the very least actively attack all network traffic), and potentially of the whole computer (I don't know if there's an exploit for that, but once you have access to the PCI bus, I doubt that much is barred). Interestingly, this vulnerability is easiest to exploit on a computer that's switched off, since the bug is in a remote management protocol parser, which in particular handles wake-on-LAN.
Yet another example is reflashing a hard disk controller (presented at OHM 2013).
This question asks for firmware on video cards. As I write, no one has given an example of a malware in the wild, but the possibility is definitely there.
There is no real protection against compromised firmware on a typical PC. You'd need to keep track of every single piece of flash memory in the computer. There are efforts to require firmware to be authenticated; on PCs, the most advanced such effort is the TPM, which currently can check the integrity of the BIOS and the OS bootloader, if you have the required hardware and a BIOS that supports it. I'm not aware of a PC where all components have their firmware checked for integrity (at least, before they're allowed to access the PCI bus). There are similar efforts in the smartphone world leveraging security features of ARM chips, but again it's a far cry from the existence of security feature to the inclusion of all firmware in the trusted base.
In practice, if you aren't a high-profile target, you don't need to worry much. There aren't any exploits in the wild at script kiddie level. But the possibilities are rife for your attacker with technical skills (or the means to hire a skilled hacker).
Firmware attacks are becoming easier over time. At Black Hat USA 2012, Jonathan Brossard presented “a generic proof of concept malware for the intel architecture, Rakshasa, capable of infecting more than a hundred of different motherboards”. The proof-of-concept (not publicly released) infects many BIOSes and common peripherals including network chips. It's only a matter of time until such firmware infection frameworks appear in the wild.