The resolution to this paradox is realizing that the electrons are originating from two different states if photo-emitted from surface A and surface B. That is, the initial states for your two scenarios are different and have different binding energies.