align-items flexbox en Internet Explorer

Tu problema puede deberse a que IE necesita una altura en los elementos para saber cómo alinear verticalmente el contenido de ese bloque. Lo podrías solucionar simplemente colocando una altura al elemento y creo que con eso lo tendrías listo.

.bloque { 
  display: flex; 
  align-items: center; 
  min-height: 80px; 
  padding: 0 20px; 
  height: 200px; 
} 

El problema es que no puedas marcar la altura de los elementos, en cuyo caso quizás tengas que buscar otras alternativas para la alineación vertical. Ahí depende de tu caso concreto y de cómo sea el contenedor donde estás colocando los elementos.

Igual simplemente jugando con el padding-top podrías darle una distancia de la parte de arriba que simulase ese alineamiento en la vertical. Tal vez, como sugerencia, te podrías olvidar de ese problema y lo del padding puede que no sea algo tan negativo, si lo que se trata es que las cosas no se te peguen a la parte de arriba de tu contenedor.

Depende de qué versión de IE estés focalizando, o igual de Edge. Supongo que flexbox funcione mejor en Edge. Ya en navegadores antiguos de Microsoft no se puede esperar que corrijan esos bugs.

Puedes probar con el prefijo -ms-flex-align de Interner Explorer 10 para alineación vertical, ya que esta propiedad solamente se añadió en IE11:

.bloque { 
  display: -ms-flexbox;
  display: flex; 
  align-items: center; 
  min-height: 80px; 
  padding: 0 20px; 
  -ms-flex-align: center;
}

Asimismo, es recomendable ponerle al contenedor una altura en Internet Explorer, para que sepa cuánto espacio disponible tiene para alinear verticalmente.

.bloque { 
  display: -ms-flexbox;
  display: flex; 
  align-items: center; 
  min-height: 80px; 
  padding: 0 20px; 
  -ms-flex-align:center;
  height: 80px;
}