Normally if an an e-mail account is deleted, you can just remake it again, have you tried that?

Even though the account will technically be new you will still receive e-mails from things you were registered with before it was deleted.