Instead of using a shadowmap for shadows, you could bake the visibility between the terrain and the main light in an occlusion map. For each texel, cast a ray between the corresponding terrain sample towards the light, and store 0 or 1 depending on whether the ray hits the terrain or not. The intersection code can be optimized in several ways, for instance by precaching the terrain geometry instead of evaluating the fractal function on the fly.
An occlusion map has many advantages: it filters correctly, takes little memory (an 8 bit format is enough), gives you soft shadows for free and it's view independent. Of course you can tweak its resolution depending on your memory and runtime budget.
That's the approach I used more than 10 years ago for shadowing my terrains (on the CPU) and it worked very well. You should be able to prototype it on the GPU rather quickly.
Just an idea!