I've spent a couple days reading all about relief mapping (or a very similar algorithm called steep parallax mapping). Essentially these techniques implement ray tracing inside a texture map, resulting in dramatic representations of geometry without the need to render additional polygons. Key benefits include parallax tracking, occlusion, and self-shadowing again all without rendering extra modeling.
Pictures are worth 1000 words, so here you go. Note how the cobblestones appear to have real volume when the parallax mapping is used (click to zoom):
I grabbed this image from this paper presented at the 2006 I3D conference.
The best part is that the procedure is (relatively) cheap, and easily implemented in realtime when offloaded to a GPU.
I think the advantage here is that the relief map doesn't support "caves" or overhanging architecture, which greatly simplifies the ray tracing problem. Otherwise, why not simply implement the ray tracer everywhere?
The downside that I've observed is that the simulated geometry doesn't interact well with other objects in the world. For example, shadows cast by other objects may not follow the relief map. This is more a limitation of the rasterization procedure and could probably be overcome by clever shader programming.