How about this? The fastest way to get me to ignore your message is to send me an email with no subject... or even worse, Subject: (no subject)!
I can see both sides of the issue. On the one hand, I've sat there with a fully written message, agonizing over a subject line, or just wanted to send someone a link, and ended up with the "I thought you'd find this interesting" subject. On the other, I've gotten an email with no subject, and had a moment of worry about whether I was about to open a virus or spam message.
I also do customer support for our email marketing service, Listbox.com. In email marketing, you would never send a message without a subject. Your subject line is your tiny billboard, your hook, your teaser to get people to open your message. In the same vein, when following up with Mark, he clarified that what he really meant was he would never open a message from a stranger without a Subject. But those are precisely the Subjects that are most difficult to write! If I could convey my entire thought in a line, I would just tweet at you, not email.
I spend a lot of time writing for other people -- email, IM, texting, with customers, business associates, family and friends. You learn to read the cues that other people are sending, and adjust appropriately. But when you send messages out into the void, there's no history to draw on... hence the sweaty-palmed subject agonizing.
How do you feel about Subject: headers? Are you grateful to Facebook for freeing you from their tyranny? Are they a critical part of the email experience for you? Or are you perfectly ok with getting an occasional Subject: (no subject)?