Para esta ocasión no te servirá de ayuda pero aquí tienes algunas buenas opciones para evitar próximos percances:
Normalmente los ISP junto con la conexión a internet también te dan una serie de servicios como son varias cuentas de correo e incluso un pequeño espacio para hosting.
Al tener un contrato con ellos si ocurre cualquier problema te pueden devolver tu cuenta, ya que saben que te pertenece.
Correos también dispone de cuentas de correo gratuitas y que aparentemente aportan mucha confianza, lo que quizás unicamente estén disponibles para residentes en españa.
http://www.correos.es/comun/apartadoPostalElectronico/06b02-cep.asp