As part of "nuking it from orbit", is it safe to reinstall the OS using Recovery?
You are correct - a suitably advanced attacker could technically rewrite the OS on the recovery HD to point it to a bad source when you reinstall the OS.

Better would to be use internet recovery since that would require even more advanced work to compromise the firmware on the Mac. 

Best would be to bring a bootable installer from a machine you have more confidence hasn’t been comnptromised.

In 98% of the time - all of the above steps to erase the hard drive and reinstall the OS are going to be equally effective, but there are increased levels of safety to be had than just using the self-contained recovery HD.