Hi Peter,
I encountered a similar situation in 06 when i upgraded a 5.1MP5 master to 6.0 MP2, while leaving the rest of the media servers at 5.1MP5. We faced the same situation of a job first hitting error 134 before completing successfully at the second attempt.
After a lot of troubleshooting and sending explorer files to Support, they were still not able to pinpoint the problem. Our only recourse was to push for a downtime to upgrade the rest of the media servers to 6.0MP2 as well. Once they were on the same patch level, this issue was resolved.