This was my first thought too, but if you take a look at the logs I attached to previous e-mail, you'll notice that query "by key" (no-index.log) retrieves data from BOTH replicas, while the "by indexed column" one (index.log) talks only to one of them (too bad it's the one that contains tombstone only - 1:7). In the first case it is possible to "resolve" the conflict and return the proper result, while in the second case it's impossible because tombstone is the only thing that is returned for this key.
Sorry, I did not look into the logs. Thats the first time I'm seeing the trace btw. :-)

Does CQL not allow CL=ONE queries? Why does it ask two nodes for the key, when you say that you are using CL=default=1? I'm a bit confused here (I'm a thrift user).

But thinking about your theory some more: I think CASSANDRA-4905 might make reappearing columns more common (only if you do not run repair within gc_grace of course). Before CASSANDRA-4905 the tombstones would be repaired even after gc_grace, so it was a bit more forgiving. It was never guaranteed that the inconsistency would be repaired though.

I think you should have increased gc-grace or run repair within the 10 days.

The repair bit makes sense now in my head, unlike the CQL CL :-)