I'm not sure if I've missed a setting in Modest, but I've always had an issue with Modest where it seems to only 'mark' messages for deletion, and not actually delete them with one of my IMAP accounts... where the IMAP server in question runs off a Mirapoint system (IIRC, running some derivative of UofW IMAP).

The only solution I've found, which isn't much of a solution for Modest itself... is reading my mail with another client (mutt on a Unix box), which shows the messages tagged for deletion (via Modest), and of course refreshing the view causes the messages to actually be deleted.