crewmeal,
Not specifically an Apple Mail answer, more of a generic one...
If you're using IMAP, make sure your actions are synching correctly with the server.
In terms of deleting items, make sure you're actually deleting them and you run a compacting process on the server once in a while (or any time you're encountering IMAP mail list sync problems such as you describe). Depending on how you're doing things, the IMAP protocol doesn't necessarily delete items and just sets a deleted flag, so you have to make sure the expunge or compact function is run somehow.
You can check your auto-compact/expunge settings in the Apple Mail preferences in your account.
In Apple Mail, manually calling the compact function on the server is as simple as right clicking on the mailbox in question and selecting "erase deleted items", you can check Apple Mail is doing something when you use the Activity viewer (window->activity)
The IMAP protocol is fantastic, lightyears ahead of POP3, but sometimes it gets itself in a muddle. And that can sometimes interfere with email clients (be it Apple Mail or otherwise).
If the above does not solve your problem, then next step would be to undertake a local index rebuild in Apple Mail (not as arduous as it sounds).