When using IMAP messages never get deleted right away. Depending on the client your using there are different ways to go about deleting IMAP message. With Outlook Express there is a Purge button, that button will delete the messages with a line through them. If you dont see the button go to View > Layout... > Custimize Toolbar > Purge
Almost all IMAP clients work this way.