You didn't say if this is IMAP or POP3 service, but from the server settings it must be POP3.
You said that if you delete mail on the Droid it does not delete them on the server as it's setup to do. If you check mail later from somewhere else it's still on the server and downloaded, correct?
But you also say that when in Outlook or webmail and you delete mails it does not delete on the server, so that if you check mail on the phone later it's still on the server and downloaded, correct?
From what you said, (and read what you wrote again carefully because it doesn't exactly make sense) apparently mail is not being deleted on the server from the Droid, Outlook or webmail. So...
1. Apparently the Droid is not deleting mail on the server as set to do.
2. Apparently Outlook is not set to delete mail or is failing to do so.
3. Webmail is not deleting mail, because like Outlook it is either not set to or failing to.
Now, #1 is no surprise. Your email app may not be communicating with the server properly. POP3 email service can be a little iffy that way. You need to check settings for #2+3. But since mail is not being deleted on the server no matter where you delete it from it could be an att.net problem.