First of all there is some serious "cheating" in the MFCC reconstruction experiment you linked to: not only the MFCCs are used, but also the voiced/unvoiced bit and the pitch.
MFCC are not speaker independent. In fact, they are used for speaker identification/verification tasks!
The speaker "idiosyncracies" are both in their prosody (preserved by this reconstruction experiment because the pitch is provided as a side-information to the reconstruction process) and in the articulation/timbre (preserved by the MFCC).
Two ingredients are needed to get MFCCs to work for speaker-independent recognition:
Vocal tract length normalization. A linear transformation (matrix multiplication of the MFCC vector) can map relatively well the MFCC sequences of two speakers speaking the same sentence. So even if MFCC are not speaker-independent one can optimize for a transformation matrix that "flattens out" the speaker-specific details.
Acoustic modelling. Using a large number of gaussians (or any classifier with large capacity) for a specific acoustic unit allows it to capture all the variations.