tramain is correct. ON my mac account and my exchange account this happens almost immediately. but on my cox cable account this takes some time but it does happen.
Let with email on any device it will depend on whether you're using IMAP/Exchange, or pop3. Pop3 will require a 2nd connection to the mail server to delete.