Make sure to check in your email client that you do not have the option set to keep them on server until you remove them, if such option exists that is.
IMAP would always leave them on server though as that is a protocol that lets you sync with multiple clients (devices) if needed.
While the option suggested by lylex10h works for removing email I would probably rather have suggested to login to the webmail (accessible from cpanel) and remove them that way.
The inconsistency is probably due to how they were deleted, it should sort itself out given time as far as I'm aware.