"Now and then" does not "logically" mean "all the time." It might, however, be ambiguous between a reading on which it means "all the time" (as it seems to mean in the phrase "both now and then") and the reading on which it means "occasionally".
"Now" and "then" can be used deictically to refer to momentary instants (as in "Now it's midnight"), longer periods (as in "Now it's August"), or much longer periods (as in "Now it's the 21st century").
Used to refer to instants, "now and then" can thus communicate something's happening at sporadic moments, or occasionally. I'm not sure about the exact history of this use though.
EDIT: "Every now and then" is an interesting variant. But it doesn't raise any special problems.
Just consider that often when we use "every N" (where N is a noun) we don't actually mean to be speaking about every N in existence. When I announce to a class that "Every student is here," I don't mean every student in existence, I just mean "Every student enrolled in this class is here." Quantifiers like "every" are said to be contextually restricted.
A similarly restricted use of "every" would explain the meaning of "every now and then" as denoting sporadic moments.