Sure, and if it fails move it to the spam folder. In the article Microsoft are discarding emails because the sender hasn't got much of a reputation yet. That's a very weak reason.

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.