Reference for an unknotting move
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".
At someone's suggestion I emailed Jozef Przytycki, who kindly sent me the following reply:
It is still an open problem (proven for knots of 12 or less crossings). I call this 4-move conjecture (Nakanishi 4-move conjecture). For links of two component, conjecture is that the target is the trivial link or a Hopf link. The possible counterexample is a planar 2-cable of trefoil (so 12 crossings). For 3 or more components nothing like this is possible (even if link is link homotopic to trivial one).
Look for example at: https://arxiv.org/abs/math/0309140
Is "region crossing change" the sort of move you're looking for? Here's a web page with a link to a news article (in Japanese) and a article preprint (in English): http://ldtopology.wordpress.com/2011/06/19/knot-theory-gets-covered-by-asahi-shimbun/