when you try to print a map service from ArcMap at higher resolution, it requests for a larger image. Since default max image height and width is 2048, mapservice never returns image larger than 2048x2048 even when ArcMap asks for 9000x9000 image. That image gets stretched to fit the area on your layout hence you get pixelated output.
you need to increase the default maxImageHeight and width.