I have been using Evolution for ages.

Even with Google its playing right, its google mail that chooses to fsck with things.

Something in your configuration of your IMAP server is screwed and ignoring the removal of deleted messages.

I had that turned on for a while... on my Courier IMAP server. Where a deleted messages was only flagged as deleted and ignored by the server, but in reality was still there.

Unless this is a new occurrence, its one thing you are going to need to check on.