|There is one other place it could be and that is inside the Master Boot Record. Once the MBR is created nothing will remove it except zeroing the entire hard disk, sometimes erroneously called a low level format.|
Deleting partitions just modifies the MBR but doesn't delete it and does nothing to the section of the MBR where a virus could reside. Formatting doesn't go anywhere near the MBR.
Do a search on Google, there are plenty of free utilities that will wipe a hard disk clean removing everything from the user accessible areas.
The chances of there being a virus in the BIOS are extremely remote. Modern BIOS have write protect systems built into the to prevent a Virus from getting in.