Ben… I realize you posted your reply over a year ago on 8/29/11; however, I had to let you know how valuable your suggestion to add noise was. I have a number of high quality, black and white, artistic images taken by a professional photographer that contain subtle gradient shades of grey that look exceptional while in Premiere Pro but blotch up and degrade in visual quality once exported. I tried exporting to nearly every single format combination possible without success; however, adding just 1% noise in Photoshop first was enough to exponentially enhance the final exported vid.
Thanks so much for taking the time to share your expertise, as I searched for hours to see what options were available, and this was the ONLY bit of info on this particular issue.