Is this by any chance a recycled brand name machine (i.e. Dell, HP etc)?

Sometimes they have hidden utility partitions which you can boot from by pressing a key during the BIOS startup.

I'd find and boot off a utility disk (like Hiren's BootCD although it's not exactly legit) and run something like partition magic. Remove all partitions and start again.

Alternately low-level format (which is not like the old days and is perfectly OK) using the drive manufacturers utility. Obviously this wipes everything.