@OP -
1) First, and most importantly, I presume you know that to minimize banding, your camera absolutely MUST be on manual exposure mode? In addition, manual focus mode is definitely preferable to auto-focus.
2) Second, I presume you realize that all camera / lens combinations, even top-of-the-line, $2000 Zeiss manual focus prime lenses, exhibit some degree of vignetting. In other words, every image they produce is slightly darker than it should be around the periphery of the image. On many low-end DSLRs with the kit zoom lens, this effect can easily exceed 1 or 1.5 stops of darkening, especially if used wide open. So, if you don't take care to minimize this, you (or your stitching algorithm) will have a vastly more difficult task to perform.
The easiest (and best) way to remove this problem is to use with a camera / lens / f-stop combination that exhibits only a small amount of this behavior. Then, before stitching, process each image through either ACR or LR and use the "Lens Correction" facility to reduce the amount of vignetting by a large factor. If your lens / camera combination is in their database, this step is completely automatic - it's just a single button-push.
3) If, in spite of taking all of the above precautions, I discover that there still is banding after using good stitching software, I find that a few applications of patch tool to be far and away the best method to remove it. The content aware fill tool also seems to work quite well, but since it made its relatively recent appearance in PS, I haven't done very many vertically stitched images, so I have less familiarity with it for this application. IMHO, for horizontal sky banding, either of the above runs rings around the clone/stamp or smudge tools.
As with all digital imaging problems, it's vastly better to minimize the source of the problem (ie, my suggestions #1 and #2, above) rather than trying to put a band-aid over the problem (ie, #3) in post processing.
HTH,
Tom M
PS - I also presume you have thought about holding the camera in portrait orientation so that you don't have to stitch together as many images to cover the sky?