The only way I see that happening is if you are using G-Mail with a mail client on the desktop, set as POP rather than IMAP. The best way to delete mail from the newest G-Mail app is with a (very quick) swipe.
I have noticed that if I delete emails in gmail and then go to the web version of gmail, those emails are still there. If you hit refresh, a lot of times it'll recognize it right away, but generally it'll take 5 minutes to be done automatically.
I think I figured out the problem. I turned off email sync awhile back because of how often it was keeping my phone awake. I guess I assumed that when I refreshed Gmail on my phone, it would refresh on the server that I had deleted the emails. We will find out this evening when I am back on my computer. For the time being, I just turned off notifications