I'd suspect a locking problem; have you made sure that no other mail-related process is trying to access the mailbox while you're deleting the unwanted messages ?
You haven't said anything about what type of OS and/or Mailbox you have. If things are happening on Linux, you might see which processes concur to access the mailbox using