OK, it looks like the procedure to have deleted EMails permanently removed is:
"I had the same problem. Solved it by going to Mail, Preferences, Accounts, Mailbox Behaviors. Deselect 'Store junk messages on server' in Junk and Trash. Also select 'Delete junk messages' and 'Erase deleted messages' when quitting mail."
From what I understand, that first option, "Deselect 'Store junk messages on server' in Junk and Trash", only applies if you have an IMAP account with your ISP. I have a POP account, so that does not apply to my situation.
See if that helps.