We are confusing here two slightly different, yet related puzzles. The first is "given word string s, parse it correctly" (the "had had" puzzles) while the second is the seemingly harder "generate a word string conforming to an unusual constraint that satisfies the rules of grammar" (the "and and" puzzles).

Obviously, TenMinJoe provides an excellent (IMHO) 'solution', that is perfectly valid. However, it would be marked wrong in an exam - why? Presumably, because it follows the letter and not the spirit of the test. However, even the first ("had had") puzzles have potential solutions that could be considered 'invalid'. Consider:

John, while Mary had had "had," had had "had had." "Had had" was correct.

To save you straining your eyes, this is simply a symmetry reversal* of the situation. Possibly a politically incorrect one, since it is now Mary who is wrong! :) In any case, it is clear that there are several possible solutions - there is no unambiguous way of parsing the sentence. Just as with those annoying "series completion" tests you get in IQ tests, a purely mechanical approach to determining the 'correct' answer is doomed to faliure.
*I'm currently distracting myself from combinatorial graph generation, which is why this looked obvious to me! :)