We send out newsletters / bulk mail (double opt-in of course). We automatically delete hard bounces (mailbox unavailable, user unknown, host unknown...) right away from our mailing lists.
But a lot of "Undelivered" mails are generated because the user's mailbox is full / the user is over quota. So the email address still exists, but the mailbox is full.
So the two most common scenarios are probably
a) the user is still using his account and will delete some emails in the near future so he's not over quota any more and can receive emails again.
b) the user abandoned his account (for whatever reason), it ran full and that's that. It will never be used again...
So the first scenario tells me to NOT delete the email address from our mailing list, the second scenario tells me I should delete it. Of course, I don't know.
What's the best strategy in terms of working on the "reputation of my mail server / IP address"? Should I try to send for the next few days / couple of weeks and if it's still not working, should I treat it as b)?
I would assume that most ESP would delete inactive / full email addresses after a certain time so they will become hard bounces anyways? Or would an ESP discourage sending mails to a full mailbox too often?
Your mail server should retry when mail delivery is deferred. Do use a less aggressive retry policy such as after 1, 3, 6, 12, and 24 hours before failing. You could also retry after 2 and 4 days. If the newsletters are time sensitive you may want an even shorter retry period. You are unlikely to get penalized for retrying after a temporary failure, such as mailbox full. You may be penalized for and aggressive retry policy. I've seen servers retry several times a minute until they succeed.
Some organizations will pass temporary failures to a second server dedicated to handling retries. If you do this, don't continue passing it to different servers.
If you send out mailings more than once a month, consider temporarily suspending addresses that bounce from the retry server. Tacking how long an address is bouncing due to long term temporary failures (delivery success rate). Consider dropping addresses that have failed for a few months.
You will accumulate dead addresses as not all organizations will bounce dead addresses. Consider sending messages asking the users to opt-in again every year or so. While you may not want to drop users immediately, you may want to drop them if they haven't responded for two or more years.
EDIT: Overquota/mailbox full is not the only reason you will get messages deferred. You should retry all deferrals on a reasonable schedule as listed above. The server will defer connections if it is to busy. Greylists will defer messages from new servers that don't are not whitelisted. My server also defers messages from servers that fail various policy checks: SPF, rDNS (IP address), rDNS (HELO/EHLO if not matching IP address) etc. My greylisting is per network block, but my policy listing is done by server. My policy list would apply to Microsoft controlled services if they weren't whitelisted. Otherwise my policy lists have been catching spam bots, and junk mailers.
RFC1893 - Enhanced Mail System Status Codes: