I would like to recommend G-mail from
Google for this.
P.S.: You might want to check your contract with Verizon, as it may be a contract violation for them to purposely block e-mails that you haven't specified.
EDIT: This should've been a response to Readysetgo, not Riamus. Clicked the wrong link. Sorry.
