Nick - are there any layers that are NOT dynamic? If so, you could put these base layers in a different mxd, create a separate map service, and perform tile caching. You could then have the dynamic layers as a separate map service. Doing this probably won't solve all your problems, but may solve half of them.
Also, when you have a cached map service within a web application, the I'm pretty sure web application becomes constrained to those tile scales, even if there is an uncached map service too. This means that if your cached map service has 8 different cache scales (for example), then your final web application can only be zoomed to those 8 pre-set scales. I think a lot of your display problems may be occurring when the user zooms to "in-between" scales, where symbology and labeling is not optimized. With caching, and a finite amount of viewing scales, the scale-thresholding in ArcMap becomes a lot more predictable and testable.
For example, if you cached a base map (non-dynamic data) at 1:12,000, 1:24,000, 1:100,000, 1:500,000, 1:1,000,000, 1:10,000,000, then you can pretty much count on the web maps looking the same as the mxd at those scales. In addition, you could set up the same scale thresholding for the non-cached (dynamic) service. When you overlay the dynamic service on the cached service, they should mesh seamlessly, and the available zoom levels of the entire web application should match the levels you set up with the cached service.
Sorry for the rambling. Some of this is a little underwhelming, but I do think the key is to constrain your scales to improve (and predict) run-time rendering.