Maybe the slightly off the topic of whether there are hard unknots but here are a few more comments about detecting unknots. Regarding complexity theory as Bill mentioned detecting the unknot is NP. Agol has also proved that it is co-NP (i.e. proving that a knot is not the unknot is NP). My computer science friends tell me that such problem, simultaneously coNP and NP are thought to be polynomial time.
So far this thread has mentioned Haken's algorithm and its descendants, the Snappea algorithm and Dynnikov's algorithm (Marc Culler has an implementation of this algorithm in his program gridlink) link text. There is also the Birman Hirsch algorithm based on braid simplification. All of these algorithms, I think it is fair to say, involve an exhaustive search through an exponentially large set.
The various kinds of knot homologies give certificates of unknottedness of a rather different nature. A knot $K$ is unknotted if and only if $H(K)=H(U)$. In historical order the Seiberg-Witten Floer homology of the zero surgery, Ozsvath-Szabo-Rasmussen knot homology and Khovanov homology are known to detect the unknot. The later two have combinatorially definitions which are rather easy straightforward to code up on a computer (making the programs run fast is a non-trivial task). Khovnanov homology having been around longer has rather good algorithms at this point. All the algorithms run however in exponential time. Since Khovanov homology determines the Jones polynomial and computing the Jones polynomial is a known computationally hard problem Khonvanov homology is likely also hard (unless by some miracle computing the group without the bigrading is computationally simpler). The OSR knot group on the other hand determines Alexander polynomial which is polynomial time computable so there is some (I think extremely slim) hope that the OSR group is polynomial time computable. In any case these algorithms have a rather different flavor, they do not involve an exhaustive search on the other hand they require dealing with exponentially large matrices. They do not tell you how to unknot the knot even if you know it to be so.