When I think of video banding, it’s usually when I create a gradient like in the examples here (just want to make sure we are talking about the same thing):

If the video is for HD delivery, Kevin Camp’s offered a recipe that has worked well for me in the past.
as for banding, you can usually add an adjustment layer with the noise effect on it. it shouldn’t take much noise (less that 5%) to hide the banding.
Roland Kahlenberg offers some notes if for web delivery.
Blurring one or more of the color channels does a better job for reducing or eliminating banding problems. Adding noise more to a comp which may be destined for Web delivery will only result in a poorer quality web version as compressors usually have a harder time compressing noise.
Use Effect>Channel Blur and increase one of the values to solve your problem. You can tell which channel needs more attention by looking at the individual color channels in the Comp Panel prior to applying Channel Blur.
Johnny Cuevas, Editor
Thinkck.com
“I have not failed 700 times. I have succeeded in proving that those 700 ways will not work. When I have eliminated the ways that will not work, I will find the way that will work.”
—THOMAS EDISON on inventing the light bulb.