I can't find any documentation that refers to using Prodigy wit Verizon, so I am going to give you two things to try that can be the cause of the error messages.
Stop using e-mail scanning & create a new Outbox and Sent Items folder.
1: Remove your AV program and reboot. Do a custom installation and when e-mail scanning is offered, uncheck it.
2: Create a new Outbox, and Sent Items folder.
Do the following for the Outbox, and Sent Items after you move any messages you wish to save to a local folder you create.
Tools | Options | Maintenance | Store Folder will reveal the location of your Outlook Express files. Write the location down and navigate to it in Windows Explorer or, copy and paste it into Start | Run.
In WinXP, Win2K & Win2K3, the OE user files (DBX and WAB) are by default marked as hidden. To view these files in Windows Explorer, you must enable Show Hidden Files and Folders under Start | Control Panel | Folder Options Icon | View, or in Windows Explorer
| Tools | Folder Options | View.
With OE closed, find the Outbox.dbx and Sent Items.dbx file and delete them. New files will be created automatically when you open OE.
If this does not help, then I hope someone else jumps in with an idea.
Bruce Hagen ~ MS-MVP [Mail]