It is difficult to answer could be some problem with the synchronization between your account and the Gmail app, have you logged in via the web and tried deleting the email? if you experience the same error there or not?
What E-email app do you use? If you use 3rd party one like Samsungs own app then it only copies the mails from Gmail. Via IMAP method, so everything you delete there may return up on re-sync. Since it does not delete on Gmail itself due to IMAP method. To get those deleted permanently use official Gmail app to delete the mails in the trash.