I had the same Issue [SOLVED]
I had exactly the same issue, suddenly the deleted emails from my BB remained on gmail and even as unread.
This happened to me after trying to fix a Blackberry from a friend, ...
I tried removing the service books and re-sending them several times, etc.. I even Tried to setup my BIS account with a blackberry that is not being used...
I was looking for this several hours, and I noticed that didn't only happened with GMAIL, was doing the same with my email from work, I was able to send email and they showed on the sent items on GMAIL and my work email.
Gmail was showing the sent emails as unread/thread conversation, very annoying.
Before deleting service books, I used the other handset and was able to to the syncing on the other handset (but is not mine), the other handset was able to mark unread items from gmail web instantly, delete items ont he handset and this items were deleted from the gmail web right away, Finally I decided to wipe my blackberry (9700) and add the emails again and everything is back to normal.
Is kind odd of what happened and what is the issue to cause this.
On my work email happened the same, read emails from BB not mark read on my exchange, after wipe is doing that as is supposed to do.
I thought it was a configuration problem with gmail but as happened that same with the other email I got the conclusion that something was wrong on the Blackberry not the email server.
I think this happened because I tried to set a different BIS account on my Blackberry, I did a device change on the other BIS account and added mine, I think that's why everything was screwed. The strange thing is that I resend the service books like 20 times, seems like was a configuration on the device memory, I tried adding a different email, one never added to the Blackberry and did the same. So' is something with the device switch but I switched the device with another one and didn't result.
Hope this information helps to anyone, I was like 4 hours searching for a solution to this.