As far as I know A2R10G10B10 format is supported in full screen modes and should give less banding if your monitor supports more than 8-bits per channel. DX SDK even had a sample about it.
The problem you are describing is difficult to handle, but typically you won't notice the problem since most of the surfaces are textured and texturing hides the problem pretty well.
Cheers!
What monitor on earth except a handful support more than 8 bits per channel? Those things are fantastically expensive and obviously supporting that is not a consumer thing.
Some type of dithering is definitely the way to go here.