Maybe use D3DXIntersect() to determine the distance between the entity and the ground?
What it does is to take a Mesh and two vectors. It loops through the mesh (terrain) and checks if any of the triangles in the mesh collides with your vector. The results are in the out parameters.
Have your Entity position be the *pRayPos paramter, and the D3DXVECTOR3(0,-1,0) as the direction vector (straight down).
Or if you want to know the distance to translate your entity up and down. Use a distance from a plane much lower then the terrain and you can get the exact height of the terrain based on your entity planar position
Will it a bit slow? For instance, if I take a simple height map 128x128, then in this case there are about 16384 vertices and let's say 5461 triangles. it will definitely take too much time for checking. Is there another way? Will be position tracking for each character a good idea? How it was done earlier?