We had the same problem and forced our users to format the cells as 'text' before entering the value. That way Excel correctly stores even numbers as text.
If the format is changed afterwards Excel only changes the way the value is displayed but does not change the way the value is stored unless the value is entered again (e.g. by pressing return when in the cell).
Whether or not Excel correctly stored the value as text is indicated by the little green triangle that Excel displays in the left upper corner of the cell if it thinks the cell contains a number but is formated as text.