Ok, think I've got a solution to issue #1. It was due to the way our organization had originally created the source mosaic datasets that the image services were pointed to. My hunch is that they were created 'incorrectly', or at least, not in the best practices manner.
Our organization maintains a series of mosaic datasets for our various orthoimagery flights; they are all divvied up by year (eg. 1995, 2004, 2013, etc) then further divided into two types: clipped to our city limits and the non-clipped mosaics (you know, the grid-like orthos that have boxy look which 'leaches' into surrounding counties outside the typical AOI). For the creation of the non-clipped mosaic datasets, we simply pointed them to the source tile images and created the dataset. But for the 'clipped' mosaics, we pointed the source imagery to the non-clipped mosaic dataset and manipulated the boundary to only show imagery within the city limits. In other words a mosaic dataset was pointed to another mosaic dataset as its source imagery; probably not the best approach, but it seemed to work well until this print issue was discovered.
After much trial and error I narrowed it down to these city limits clipped mosaics. Every time I tried to create a new, test image service, it would fail during cache creation (ERROR 0001456: Failed to update tiles). This error would only occur on these particular 'clipped' mosaics. Unfortunately it was extremely difficult to narrow this issue down because all our image services were pointed to these city limits clipped mosaic datasets, so they were all uniformly incorrect. Just took a lot of trail and error with sample/test datasets.
Additionally, I am unsure how we were even able to create the original image services years ago given all of the difficult I encountered with testing. But right now I am creating all of our source mosaic datasets and rebuilding the image services too. Time-consuming, but at least it's being done right.
As for issue #2, still working on troubleshooting this problem. Got an ESRI ticket open right now.