Well this always happens on IMAP accounts, whether you can see it or not. If you don't want to see the messages marked for deletion, there's a suitable option on the View menu. On Outlook 2003, it's counter-intuitively hidden under View-->Arrange by-->Current View. (What genius at MS thought of that naivgation path? Bozos!) Bear in mind that the messages will remain on your ISP's server until they are explicitly deleted ("purged") unless your email client auto-deletes.
This is all because of the way IMAP works. It's by design. Personally when I'm using Outlook and deleteing IMAP mail, I first hit DELETE, and then press Alt-E, Alt-S - that's the keyboard shortcut to purge. It's become a habit.