I've had this problem before and can't recall how I managed to fix it last time. I use Apple Mail to access my Gmail and normally flagged emails show up correctly. Starred emails in Gmail equate to flagged emails in Apple Mail and I can unflag an email in either Gmail or Apple Mail and it works.
But now I've got four emails that I can't unflag. They're not flagged in Gmail at all (although they used to be). When I see them in the Flagged folder in Apple Mail, they don't even have flag icons next to them but they're still counted in the number showing next to "Flagged". If I manually re-flag them and then unflag them, they disappear from the Flagged box. But then if I click into Inbox and then back into Flagged they show up again.
Any ideas about how to make these guys disappear for good?!