Here, fast doesn't mean "(capable of) moving quickly". Much rather, it is being used in the sense "firmly fixed" (see fasten your seatbelts or fast friends). The Phrase Finder says that "This is a nautical term. A ship that was hard and fast was simply one that was firmly beached on land." It adds that the term was used in figurative sense by the early 19th century.
Personally, I don't think it's being used more commonly in the negative. Indeed, a quick COCA search returns 40 occurences of "hard and fast rule" or "hard-and-fast rule", but only 22 of them are using it in a negative context — and I am being as generous as possible there, counting not only "no hard and fast rule" and "not a hard-and-fast rule", but also "don't have any hard and fast rule", "rather than any hard and fast rule", "was never a hard-and-fast rule" and the like.
One thing stands out to me, though: out of 16 occurrences of "hard-and-fast rule", with hyphens, 12 appear in a negative context, or 75%. For the non-hyphenated version, it's almost the other way round: 60% positive, 40% negative. (Again, counting "negative" very generously.)
The figures from the BNC are too small to be statistically meaningful. But anyway, here's an overview:
COCA BNC
total negative total negative
hard and fast rule 24 10 8 7
hard-and-fast rule 16 12 1 1
From the Online Etymology Dictionary:
Open-and-shut "simple, straightforward" first recorded 1841 in New Orleans.
No further information on the origin of this phrase is available from the other sources I checked.
Open-and-shut is certainly used in the positive sense. In fact, open-and-shut case is a common expression. Two examples:
And I also discovered that this phrase (open-and-shut) is extremely popular in golfing circles (think Open) with the hyphens dropped (open and shut or Open and shut). Examples (headlines):
Best Answer
The phrase comes from boxing, when one fighter would challenge another and require him to put up a stake for a match, or stop his fighting words.
1858
The OED's earliest quotation is:
Here it is printed in another newspaper with more context:
Cambridge Chronicle, Volume XIII, Number 32, 7 August 1858
1865
The earliest I found in the Chronicling America archive from 1865 makes the meaning clear:
The Montana Post, July 15, 1865 (Virginia City, Montana Territory [i.e. Mont.])
1867
The next I found is also a boxing challenge in The Montana Post, November 09, 1867. After that, it's used referring to a bet: put up your money to take on the bet or shut up.