Behind, around and through hieght maps?

Height maps are useful in most instances, but upon trying to model a sponge, it’s quickly apparent that height maps can’t render a cave-like structure, or can’t render geometry that is multi-valued with respect to a height function. Is there a way around that, to give height maps a more twisted effect so that the turn in and out of a particular perspective? Maybe there is some kind of way to composite height maps, one based on the z-direction, the other based on…UV coordinates? Normals?

You could try vector displacement.
Or a thick volume shader with a bunch differently sized voronoi textures.

can be done with volume and some texture

see this

happy bl

You might want to take a look at OSL.

You can combine the disp modifier with Cycles shaders to twist the intiail normals direction. Cycles material output can bend/scale the normal one final time via the displacement node, that is during the final position calculation. So, do as much as possible with the geometry then add further details in the material.