It's one of the holy grails of 3D-dom... No kidding.

CGSociety (cgtalk.com) just had an FX Wars on that very subject because it IS that hard to do well.
I wish i could be more inspiring, sorry

I would suggest trying to use MetaClouds grouped (LOTS of them), forming the cloud. Maybe you could animate them by "groups" to suggest the build and size, etc.

Good luck-

-Lew