The specific issue that this affected: Clients with PCs pointing to WEB2 WS4.5 (after a weekend update from WS3.5 to 4.5) that were using the "Label - Laser" Label Printer type.
We isolated to this being a Web2-based issue by testing client PCs that we assumed were, but then I pointed the Registry's WS Address to the localhost WS endpoint. Once I did that on both Web Servers, I was able to pinpoint the failing Server. At that point I was beyond my means, RL Tier-1 Support couldn't find the solution, neither could Tier-2 Standard Product team, and it was escalated to Brad. Quickly Brad was able to tell Tier-1 the resolution.
Resolution: On the Server that sees the issue, verify that the RateLinxWebService (3.5 & 4.5) Application Pools are using "Network Service" Identity.