All DirectX 10 GPUs can do vertex texture fetch (just tried running NVidias Direct3D9 VTF demo on ATI Radeon 4850). They can also use all available texture formats, not just FP32 (but this may work only in D3D10?).

I had similar problem once (it was OpenGL program and vertex texture lookup doesn't work there even for new ATI cards). I used 2 buffers as you wrote earlier. I had a static triangulated 2D grid which was reused for every terrain block. Scalar height values were in separate buffers (one for each terrain block).