So huge "cloud" textures across the entire bottom of the map would be a bit framerate intensive, I gather. I would of course still want the map to be playable for everyone, so that option doesn't fit. Would big particle systems be more practical? I feel like that would be a lot simpler and more efficient, in addition to some 3D skybox env_fog_controller'ing. Actually making the particle system would be quite a challenge, though.
The problem is, as xzzy mentioned, translucent materials in general. Whether it be single large faces or lots of particles. An opaque pixel only needs to be handled "once" (lets ignore shaders and yadda yadda here), and will simply render instead of whatever is behind it. If you have a translucent pixel, it has to be added to whatever is behind it, meaning two things to handle. So on and so forth. If you used 10 cloud sheets to gradually make it foggier, each pixel would have get 11 things blended together.
A particle system with large overlapping sprites would suffer the same way. That's the reason you could make an extremely crazy sparking sprite (like a saw cutting metal) and it wouldn't hurt the framerate at all because the sprites are tiny and will rarely overlap each other. Whereas if something like the payload explosion smoke starts to fill too much screenspace it can cause a slowdown because the sprites are huge.
On top of all this... if it gets put in the 3D skybox it will be rendered at all times, because that's just how skybox is.
Now for an actual idea I just had... you might be able to get something that looks pretty good if you hand-draw the clouds to match your map. That is, make one single large (2048^2 or more) non-tiling texture that you would scale up huge and the clouds would "fit" in your valley, and fade out before they reach the hillsides so you don't see a line where the face cuts through.