All of my messages with emojis are in trash and have been long before I started researching this problem. I do not see a way to "delete forever".  Another interesting/troubling thing is that my "All Mail" folder shows messages on my iPhone but on my iPad that folder is also empty (sent folders empty on both).  

If emojis are the issue, I don't see a way to get them out of the trash.  There is no "delete forever" button.