How to write cold emails that are not spam

Unsolicited commercial email ("cold emails") are spam; specifically, legal rules -- both state and federal (e.g., CAN-SPAM and its implementing regulations) -- designed to fight spam target unsolicited commercial email generally.

The definition you post reflects the original, Usenet-era, definition of "spam" when the term was being applied to newsgroup posts (not always commercial) that depressed the signal-to-noise ratio on newsgroups. However, once email harvesting, often combined with superficial personalization, began being used to send cold commercial emails, the term was applied to unsolicited commercial email generally -- and this was a bigger concern for the internet community (and the public at large) than the old kind of "spam" ever was, resulting in various legal efforts to control it.

This is called Unsolicited Commercial Email (UCE), which by definition is spam. If you are sending someone email with hopes to sell them something, it doesn't matter how nice you are, it is still spam. Cold emails are spam.

http://en.wikipedia.org/wiki/Email_spam