If MFCC vectors are speaker independent, then how can we reconstruct unique speech signals from them?
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.