The way that I would approach this problem would be using the machinery of claspers. Below, I use clasper language freely because I know that you are familiar with it. Your move implies that clasper edges behave like combinatorial objects- I can delete twists in them, and pass clasper edges through one another.
Begin by untying the knot using clasper surgery (for example using Y-claspers only, by unknotting using delta-moves, as in Murakami-Nakanishi/ Matveev). I don't need to remember twisting and linkage of edges thanks to your move- only the position of the leaves, and the combinatorial structure of the clasper (uni-trivalent graphs which end on the leaves) matters.
Next, I notice that the result of a Ck-move, if it happens inside a small ball with one unknotted line segment and no other clasper leaves inside, is ambient isotopic to a line segment whatever the combinatorial ordering of the leaves I think (draw it! The picture unravels "from the left". An illustration is Diagram 32 of http://www.math.kobe-u.ac.jp/publications/rlm15.pdf). [Edit: This is true for some orderings and not others, so more work is needed at this step] I also notice that I can pass one leaf through another "at the cost" of introducing a clasper-move with one more trivalent vertex, and that I can perform a "topological IHX" move inside a clasper to reduce it to "comb form", in which it represents a Ck move.
This is enough- I choose a small ball, choose a clasper C, and pull all leaves of C inside the small ball. IHX so it becomes a Ck-move (maybe with leaves arranged in a strange order), and cancel it. I get left with a diagram with one fewer clasper (although the remaining claspers may be more complicated). Induction finishes. [Edit: It isn't clear that this process "converges"- see comments.]
This is one thing that clasper machinery is really well suited for, I think- it's the right language to discuss unknotting moves. Choose a clasper decomposition of the knot or link (replacing it by the unknot, with some tangled web of claspers inside it), identify moves on claspers induced by moves on knots, and show that they suffice to untangle the web, by pulling leaves into standard positions. To my taste, this leads to the nicest proof of "delta moves unknot".