I just recently set up a Gmail IMAP account in Outlook Express (OE), so I haven't used OE for this account much yet. Like you, I have OE set to "Purge deleted messages when leaving IMAP folders". What I've observed is that the "deleted" messages appear with a line through them immediately after "deleting" them. They remain that way until I close AND reopen OE. Yep, I see them still there immediately after re-opening OE but they then disappear with a few seconds.
Could this be what is actually happening in your system?