After implementing several new features in DirectX, including a bloom effect and a skydome primitive, I experimented with making skies that could pass as acceptable. Though not by any means blown away by the appearance of my procedural clouds (let's face it, when it comes right down to it, perlin noise doesn't look anything like real volumetric clouds), I was quite happy with the overall effect created by the skydome, the bloom shader, and a sunset-style fog.
Note that the cloud shader actually consists of a turbulent perlin noise, which gives the clouds a slightly nicer appearance than simple perlin noise would allow. Interestingly, the seed value of the noise can be animated, along with scrolling of the texture coordinate offset, to produce the illusion of moving, ever-changing clouds. Unfortunately, the technique is quite expensive, especially for high-resolution cloud maps. However, with the rapidly-expanding power of graphics cards, it may be viable to animate a full, dynamic, 1024 res cloudmap in at smooth framerates in the very near future.