How is it possible for a VAE decoder to reconstruct n different classes while being limited to much lower k dimensions? How is  this even possible for the VAE Autoencoder to reconstruct n different classes while being limited to k dimensions in the bottleneck layer (k<<n).
For an example, I created a simple MLP-VAE with embedding size of only 2 and used the MNIST dataset which has 10 classes.
To my astonishment, the model could easily reconstruct all classes with different latent varible values.
This is very puzzling to me! Aren't the mean and stds that are created in encoder's part which are as large as the embedding size, supposed to specify each classes valid values?
That is for example, all the variables that can create a 1, will have this mean and this std! while the values needed to create 2's have that mean and that std! etc) and basically the network uses these mean/stds to form separated regions, to sample from and create new digits later on?
What is happening here? Why should this even work? How and where do all these digits come from then? They cant be coming from only two means, two stds!? can they?     
 A: 
Aren't the mean and stds that are created in encoder's part which are as large as the embedding size, supposed to specify each classes valid values?
  That is for example, all the variables that can create a 1, will have this mean and this std!

This is not correct. The encoder defines a mean and a covariance (std) for each sample individually—not all ones get encoded to the same gaussian. The VAE learns to encode different samples to different subregions of the prior density, so that over the training dataset, KL divergence between the priors and posteriors is low, but at the same time, each sample's encoding contains enough information to reconstruct it.
I recommend reading the article Density Estimation: Variational Autoencoders by Rui Shu, which demonstrates it with the following figure:

An example of a 2D latent space encoding of MNIST shows it too: Overall, the latent space density is gaussian, but different classes occupy different, non-gaussian subregions (image from A Tutorial on Variational Autoencoders with a Concise Keras Implementation):

