My best guess would be that it is caused by the fact that GMail doesn't really have folders per se. It emulates them when it's syncing with your client through IMAP and the web interface shows you folder icons, but these are really labels. In the case of the "sent" label I'd guess it's just a well-optimized search over "From:" headers of all the mails stored in "All Mail". If this is the case, then it appears that this search isn't as accurate as one would wish it was.