An email that you permanently delete or move to a PST will not be recognized by the BES unless you enable Hard Delete Reconciliation.
Or do you have it enabled but it's not working? If not, then search the
BlackBerry Technical Solution Center for hard delete.
If you said that mail moved to subfolders don't delete. Those emails won't delete but they should file to that folder on the BB. You can tell if it's a filed message if the icon is a folder and not an envelope. If that's the case you need to enable Hide Filed messages.
If the subfolders are PST's then the Hard Delete Reconile option should get that working for you.