Since more than one person had this issue my guess is a restore was done at the server level & deleted entries were restored by accident. IF it continues to happen you may want to look into a 3rd party application to manage your email.
Just to clarify, 3rd party applicatins can be paid (such as Microsoft Outlook) or free such as zoho mail which I use and have had no issues with ... http://email.about.com/od/freeemailreviews/tp/free_email.htm
After a very easy initial setup and transfer of your contacts, mail, & calendars these programs often offer more features and in some cases more storage space as well as excellent support. Plus if you delete items by accident and clear the trash you can set these up to keep a copy on the verizon server.