Depends on the level of trust you place into the compromised systems and your threat model.

Basically they are going down the "nuke it from orbit" route, lets say they miss a system that reinfects the rest somehow.

As for formatting windows, sadly these days that is no longer enough to be sure with a "well crafted" malware. Lets take the industry favourite laptop tracking platform CompuTrace (now named Lo-Jack iirc).

The BIOS/UEFI Module that is its heart is a small EXE that gets executed by windows on every boot (Just like the Superfish incident, though that did use a diff way to get executed on windows launch, lo-jack gets executed by windows, superfish replaced a file that would get executed).

In Lo-Jack case its a small dropper exe that then fetches the real tracking payload once the laptop connects to the internet but it can be (iirc) tricked into downloading and running any exe it likes with system priv's. A BIOS flash of a fixed BIOS is the only "fix".

But in my past I've had fun injecting stuff into and modifying BIOS's (Mainly just to unlock extra options or remove whitelists for wifi cards) and most BIOS/UEFI's these days can be flashed from within Windows. Sure to save bricking the machine you would need to get the correct BIOS for that machine but if a company puts in a purchase order for 100 office machines they are not going to differ too much.

If you have a payload running on a machine you could call home with its motherboard make, model and revision. Download the bios from the vendor, inject a payload into it, send it back to the machine, have the machine flash it in the background and using the same methods Superfish / Jo-Jack use have malware that persists though a format or even a replacement of the drive.

I'm sure we have already seen malware using these techniques already in the wild. Signed BIOS updates will protect to some degree but their have been a fair few cases of being able to bypass the sig check (which is often only done during the the read of the bios before the flash takes place).

Is it overkill? is it paranoia? Probably. It might just be simply the case that the machines were due to be replaced at some point in the near future anyway so 2 birds, one stone.

EDIT: It might of not been Lenovo's use of superfish that was installed via bios on reinstall of Windows, but their own bloatware. It replaced Microsoft's copy of autochk.exe with its own that installs other pieces of Lenovo software. After the shit hit the fan in that case, Lenovo quickly issued BIOS Updates to remove the "feature". But it goes to show how abusing the Windows Platform Binary Table can be used to inject unwanted software into a system.