I noticed this, I would delete inbox items that would go to trash but they would not delete when choosing empty trash, and would still show in all mail and under important. Then when reopening Gmail they were back in the inbox.
It was like this for the past few days and bugging me like crazy, but yesterday everything deleted normally and everything seems to be back to normal, not sure what was going on but maybe it was server side?
Hopefully it's works itself out for you too.
Sent from my SPH-L720