If commercial software is an option, our Geocortex Essentials product is capable of creating large format map PDFs at high resolution.
Your PDF is generated out-of-process and smaller map images are fetched individually then stitched together. There's a REST interface for triggering the export and setting user-specific things (map markup, text for boxes, etc). We can combine maps from multiple services, including Bing Maps. Size and resolution are only limited by disk space and patience (it can take hours to do a poster-sized 1200DPI image)
One unfortunate side effect of printing at high resolution from an ArcGIS cached service is that the server will bump down to the next cache level if the visible scale is now closer to that level, so if you're going from screen to paper resolution, what you see is not necessarily what you get. This doesn't happen with dynamic services.
Disclaimer: I work for Latitude Geographics, though not directly on the Geocortex Essentials product.