The explanation is that the energies of the different orbitals are not actually constant, but depend on what other orbitals are filled. When both the 3d and 4s are empty, the 4s orbital is lower in energy, and so it fills up first. However once you add electrons to the 3d orbital the 4s orbital actually becomes higher in energy than the 3d. Hence the electrons are removed from the 4s orbital first.
You might expect that once you had removed the electrons from the 4s orbital the ones in the 3d would move to the 4s (as it's now lower in energy). However this d->s transition is forbidden and so this doesn't happen.