I know it is quite far down the line and I was having this same problem (even with JPGs).
I found this tech support article that worked for me:
I still have the same issue as of today when printing A3-sized pdf map. it seems the png, jpg format works fine.
My default printer for the ArcGIS servers are Microsoft XPS Document Writer, the servers are virtual machines....
If you carefully review the link above you would see that on you ArcGIS Servers you need to install another printer that has a larger than 8.5 x 11 capability.
Set ArcGIS Server Account's Windows default printer's default page size to a size as large as or larger than the page layout that is being exported. For example, if the map document is a tabloid size (11 x 17), set the default printer's default page size to 11 x 17 or larger. If setting the printer to the exact size of the layout page, check that the orientation (portrait or landscape) also matches the layout to be exported. The easiest solution is typically to install a plotter driver, as these have the largest page sizes available by default. Microsoft Windows ships with many plotter drivers available through the Add Printer wizard. No download is necessary.
I finally makes it working. I did read the article, and tried a few things on the printer drivers and after a few hours I gave up
Today I tried my plotter driver using ArcGIS Server Account, it worked! kind of strange though, I am using my own account in the custom print service, the ArcGIS Server Account doesn't work with my print service for unknown reason, but this is another story.
Thank you for reassuring me that the solution will work, and I tried it again, it worked
So - I've done the steps mentioned above and added a plotter driver with an Arch E default paper size. Still garbled legend items when the legend is at the bottom of the pdf. If I move the legend to the top then the symbology comes out fine. This is mentioned in the article linked above and then again referenced by Robert.
Is there any other guidance to resolving this issue?
I'm just trying to generate letter or tabloid sized prints. The article said to set it to the maximum print size or larger. I tried tabloid, then subsequently larger sizes. Now I'm at the maximum print size for the plotter driver I installed. Still not working.
I've also installed a different default printer just to see if that helped and it did not.