> A sole "Re:" is equally spammy, I've seen enough spam trying to hit with > just that.
I don't think we should be focusing on combating spam with these subjects. Spammers will probably pick up on any pattern we might come up with. The reason I mentioned "spamminess" is that "Re: your mail", when used by spammers, it's to actively convince you that you're seeing a reply to something you sent, but when used by people it's just seems redundant and strange. On the other hand "Re:" just signifies an empty subject. Nothing more, nothing less. It's not trying to lie to you.