Exactly, this is not "randomly losing correspondence". This is simply spam filtering that is done after accepting the e-mail for delivery. Whether that should be an acceptable behavior or not is another discussion.
If storing vaguely suspected spam is intolerably expensive then maybe just keep a list of discarded messages (sender, title and date). At least users can see what's happening.
The server rejects the message, to get rid of spammers. After a few rejected messages, they usually stop delivering SPAM for quite some time (it's unnecessary work to do, and a higher risk to land on blacklists).