Randomized algorithms using a stack
How about Welzl's randomized algorithm for minimal enclosing ellipsoids? It has recursion depth O(d) where d is the dimension of the space.

I know next to nothing about derandomization, so this might not be what you're looking for. If my example doesn't qualify (maybe by your definition it only makes inessential use of recursion?), perhaps you could clarify why that is. That would increase the chances of higher quality, more pertinent answers from others.