As you suggest, a lot of people have thought about this question. It's hard to find arrangements of an unknot that are convincingly hard to untie, but there are techniques
that do pretty well.
Have you ever had to untangle a marionette, especially one that a
toddler has played with? They tend to become entangled in a certain way, by a series of
operations where
the marionette twists so that two bundles of control strings are twisted in an opposite
sense, sometimes compounded with previous entanglements. It can take considerable
patience and close attention to get the mess undone. The best solution: don't give marionettes to young or inattentive children!
You can apply this to the
unknot, by first winding it up in a coil, then taking opposite sides of the coil and
braiding them (creating inverse braids on the two ends), then treating what you
have like a marionette to be tangled. Once the arrangement has a bit of complexity,
you can regroup it in another pattern (as two globs of stuff connected by $2n$ strands)
and do some more marionette type entanglement. In practice, unknots can become pretty
hard to undo.
As far as I can tell, the Kaufmann and Lambropoulou paper you cited deals is discussing various cases of this kind of marionette-tangling operation.
I think it's entirely possible that there's a polynomial-time combinatorial algorithm
to unknot an unknottable curve, but this has been a very hard question to resolve.
The minimum area of a disk that an unknot bounds grows exponentially in terms of
the complexity of an unknotted curve. However, such a disk can be described with
data that grows as a polynomial in terms of the number of crossings or similar measure, using normal surface theory. It's unknown (to me)
but plausible (to me) that unknotting can be done by an isotopy of
space that has a polynomially-bounded, perhaps linearly-bounded, "complexity", suitably
defined --- that is, things like the marionette untangling moves. This would not
imply you can find the isotopy easily---it just says the problem is in NP, which
is already known.
One point: the Smale Conjecture, proved by Allen Hatcher, says that the group of
diffeomorphisms of $S^3$ is homotopy equivalent to the subgroup $O(4)$. A corollary
of this is that the space of smooth unknotted curves retracts to the space of
great circles, i.e., there exists a way to isotope smooth unknotted curves to round circles that is continuous as a function of the curve.
This is just a comment. The same week (!) when Dylan asked this question, we received at our department a message from a non-professional mathematician who wrote a computer program that tries to simplify knots using level moves. (A "level move" is like an under move, but there can be more strands lying below the arc that you move.) He says that he tried all unknots he could find on the web and they can all be fully monotonically simplified in very little time (the crossing number strictly decreases at each step, as far as I see).
For instance, the Gordian knot (shown below) can be fully monotonically simplified using level moves.
His program produces nice understandable pictures, and looking at them you can easily follow the moves that unknot the knot. These are available here
He actually wrote to us to ask for more examples to test the program with (there are not so many ready-to-use examples around), so if you know more hard unknots please share them (here or somewhere else)
Best Answer
This question has been fully answered (the expected number of moves is $\infty$), as detailed in an addendum to the question. I place this community-wiki "answer" here so I can accept it and so prevent the MO software-bot from re-asking the question.