I now have a vision of an iron atom scratching its head because it can't remember which d-orbital to put an electron into.
You've got it backwards. The iron doesn't choose anything. The electron goes into the lowest energy available orbital, simple as that. In an isolated atom, all the d-orbitals are degenerate (equivalent energy). However when the atom is surrounded by other atoms, as it is in a heme, some of the d-orbitals become lower in energy than others. This is the basis of ligand field theory. If an oxidation or reduction occurs at this point, it is this ordering of energies that determines from which/into which an electron is removed/added by an oxidation/reduction reaction.