Flex es suficientemente compatible con todos los navegadores ya:
http://caniuse.com/#feat=flexbox
Y ojo. Una cosa es Flex y otra cosa es un div. El div lo puedes seguir usando, el Flex es una propiedad que le das a ese div.
Y Ojo 2... ¿Por qué necesitas un div? En tu caso aplica los estilos directamente al <a>
Y Ojo 3... Mi primer comentario es:
Cita: 2) Prueba una combinación de width con min-width.