To the original poster: did you re-create your account? Perhaps it's set up with IMAP now, whereas before it was using POP3? Or perhaps it's IMAP and the server doesn't support UIDPLUS?
The difference is that with IMAP, the app syncs "moving to deleted" with the server, so then if your mail app does not retrieve messages from there (which I guess no sane mail app would do), then you won't see those messages.
Before, if you were using POP3, or IMAP (without UIDPLUS), the app's Deleted folder was purely local, in-app, and wasn't affecting anything on the server (until the deleted folder was purged).
So my recommendation is -- move a test message to Deleted, then use web mail to see if maybe it's been moved to the server side deleted folder. That would explain things.