Samsung S2 not deleting sent emails on gmail
I had this issue in the past with my Samsung Galaxy S Vibrant. What I did, and it solved my problem was:


Go in to Settings -> Accounts &amp; Sync 
Select the gmail account with issue
Turn off sync for Gmail
Turn back on sync for Gmail


If this doesn't fully solve the issue, but it did for me, try the following:


Go in to Settings -> Applications -> Manage Applications
Select the All Tab
Find the Gmail Application and select it
Click on Clear Data and Clear Cache
If you have multiple accounts on the device, it may remove them from accounts and sync. At the very least, you will have to go back to accounts and sync to re-enable Gmail sync.


It really isn't that big of a deal to clear the Gmail data because it is all constantly sync'd with the Google servers. It will clear out any Gmail app settings you have set, like your signature on your phone if you set one.