The 80:20 ratio of software development applies to the legal system as well. Tightly specifying the legal code for the borderline 20% would require so much work and added complexity to be almost impossible. Hence we instead use the court system to decide on the borderline cases.
Generally a wide range of factors are taken into account when quoting a work. This includes the length of the quotation (in proportion to the whole work) and the context the quotation is used in.
So for example short poems (<10 words) have received protection in the past, because the 10 word quotation forms a substantial proportion of the work.
The argument for protecting headlines comes down to whether headlines are works in their own right. Given that they can stand on their own independent of the articles they're associated with means that the probably do qualify to be treated as works on their own right.
The creativity and originality criteria are tricky, it's likely that some headlines are copyrightable but others aren't. Only a court judgement can clearly but a headline in one category or other.
But as I said elsewhere, this is only relevant if you are copying from another source. If you write a headline that happens to be identical to another headline then that isn't a copyright violation (regardless of length).
Copyright prevents copying the expression of ideas. If an idea is expressible in only one or a few ways, copyright is not appropriate.
The smaller the expression, the fewer ways exist to express the idea.
Where do you draw the line between a "creative" headline, and a headline that just expresses the idea as concisely as possible?
Surely some individual phrases in the article require "a lot of time and creative work" - can those not be quoted elsewhere?
The US Copyright office has this one correct:
"Several categories of material are generally not eligible for federal copyright protection. These include among others: ... Titles, names, short phrases, and slogans; ..."
http://www.copyright.gov/circs/circ01.pdf
kb