Yeah, I usually go through it all, bin the hard drives usually, then update the bios firmware, pop in a new hard drive or SSD, and then install whatever operating system I want on it. Usually though, not many people are sophisticated enough to touch the bios side of things, but it's just for piece of mind on my end.
Well, rewriting BIOS is almost too sophisticated for myself
. I don't think I've done that (may have been doing it once many many years ago), but I may be able to find and follow a tutorial though.
Ultimately, a wipe/format should be sufficient for most people, either with dban or dd on Linux systems. Although, that usually requires connecting a USB to a possibly infected machine. So, either go the Qubes OS route, and isolate or use a Live CD of Ubuntu etc.
Iirc repartitioning the HDDs can be done even from Windows' install DVD. Of course, I have an E2B stick with plenty of iso with tools, so I have where to choose from for the job if needed, some from Linux, some even under Windows. I mean that there's a much wider list of options.
And although I've used SDelete (yes, I'm a Windoze guy) here and there, I think that repartitioning does the job and wipe is overkill.
Although, most of the time much of that is overkill. Although, I do always recommend people listening to their inner threat model, and not compromise.
The problem is that most people don't have enough knowledge and their "inner threat model" will be silent, hence troubles like those signaled by OP.