This happens a lot if you use google exchange sync to get gMail on your iPhone. If you use the iPhone Mail app to delete a message, it actually just removes the Inbox tag, but doesn't move the message to the bin. It is still visible in All Items.
If you want to actually delete the messages, you need to find them first.
I followed the above links, and installed this greasemonkey script (into firefox). I also had to disable the Better GMail firefox add-on to get the script to work.
I then had a new link on the left in gMail - 'Unlabelled'. This opened a search for all messages not tagged with any of my labels. I had to edit this search to remove mails in my Inbox - I added '-label:Inbox' to the end of the search box.
Finally I noticed that some mails picked up in this search were actually tagged after all. This happens if you use your iPhone to delete a single message from a conversation - gMail finds the single message matching the search, but brings the whole converstaion into the results. To get round this I ran the modified Unlabelled search, then selected all messages and tagged them 'Untagged'. I then pasted the search string into a text editor and replaced '-label:' with 'OR label:'. I removed the leading OR and wrapped the whole lot in brackets, then tailed it with label:Untagged. This search finds everything tagged with any label, and with Untagged - remove the Untagged label from anything in this search. Finally delete everything matching the Untagged label.
It's easier than it sounds!
Original Unlabelled search-string
-label:Label1 -label:Label2 ...
Modified to remove messages in the Inbox - tag everything matching this search 'Untagged'
-label:Label1 -label:Label2 ... -label:Inbox
After Find/Replace to find anything with a label AND the Untagged label - remove Untagged label from any matches
(label:Label1 OR label:Label2 OR ... OR label:Inbox) label:Untagged
Finally, delete everything matching this search
label:Untagged