Sorry to disagree with prj, but you do NOT want to use POP3.
For this reply, I'm assuming the account you're using is your Gmail account or another IMAP account.
Default behavior for IMAP including Gmail, is for deleted email to be sent to the Deleted folder, where it stays until manually deleted, or for a specified number of days, 30 is common, before being automatically permanently deleted. A couple of things could be happening in your case:
1. There might be both a Trash folder and a Deleted folder. Unless they are synced together, email sent to Deleted will not appear in Trash, and vice versa. If you have both, check both, and you might want to sync them.
2. Some email clients have an option to delete mail on the server immediately, bypassing the default behavior of parking deleted email in Deleted for a while. Check for that option and if present, how it is set.