What's the current state-of-the-art algorithm for ray-tracing height-fields?
For the current state-of-the-art, look for this paper:
"Maximum Mipmaps for Fast, Accurate, and Scalable Dynamic Height Field
Rendering", Tevs et al. 2008

The basic idea is to skip a lot of space by having knowledge of the maximum value over large areas of terrain. If the ray stays above that, skip to the next large area. 

If you look at Figure 8, you'll see a comparison of basic linear stepping vs. maximum mipmaps. Linear stepping results in 200 steps, which can be done real-time on modern gpus but is still actually slow. Max mipmaps do the same in about 10 steps, all in shader.