When you delete a message, it is "marked" for deletion (the Blue-X). The setting for Delete Mail Immediately determines when the message will be deleted -- either immediately or during the next mail check (default).