Are tombstones created if I execute CQL statement DELETE ... USING TIMESTAMP T where T is in the past for more than GC grace period? Does that mean that potentially the related data might be deleted only on some replicas and therefore they can reappear? (even if the statement is executed with CL ALL?)
Example: GC grace period is 5 days. Current date is January 10 and for deletion I use timestamp from January 1.
The tombstone is created in the situation you described, but it may spontaneously disappear during compaction that may start without your control.
However, if you write the tombstone with CL=ALL, i.e., you're sure that the tombstone has reached all replicas, then this tombstone is guaranteed to delete any existing data covered by the tombstone (in particular it must have an older timestamp!), and such data cannot be resurrected later:
The point is that even though compaction may get rid of the tombstone, it will get rid of the data as well. In fact, compaction may drop tombstones only it knows that it looked not only at the tombstone but also on all sstables which might hold data for the same row).
If you write the tombstone with lesser consistency level (e.g., QUORUM), this isn't guaranteed. It is possibly (although in practice unlikely) that one of the replicas will not receive the tombstone, the two other replicas will and then perform major compaction and drop the tombstone - and then a repair will resurrect the data.