Unfortunately, once mail is deleted from Verizon's servers it's pretty much gone. You can try putting in a ticket, but 99.99% of the time, you're just going to get back "nothing we can do" responses.
Any time mail disappears from the server, there's a pretty good chance there's some device pulling it off. This can happen even without you intending it to. For example, the default Verizon setup for a long time (and possibly still) configured Outlook automatically unless you were paying attention and unchecked the box during the install.
The easiest way to fix it is to change your password. Once the device(s) can no longer authenticate, the disappearances should stop.