Pues no hay demasiadas opciones.
Una de ellas es GMX. Funciona muy bien, yo tengo unas cuantas cuentas ahí desde hace años y la verdad es que van de lujo. Es curioso, porque GMX pertenece a la infecta empresa de hosting 1&1, pero mientras que su hosting es auténtico SIDA, gmx es todo lo contrario. Supongo que funcionarán completamente aparte y con equipos de trabajadores distintos.
Otra opción es el clásico yahoo, que aunque ha sido barrido como buscador por la competencia, todavía tiene muchos usuarios de sus cuentas de correo.
En ambos casos desconozco cual es el límite de almacenamiento, pero supongo que por poco que sea superará ampliamente esos 500 mb. que pides.
Otra opción es pagar y pillarte tu propio dominio y hosting. Ahí te montas las cuentas de correo que quieras con la capacidad que te de la gana hasta el límite de lo que hayas contratado.
