Dean,
I ended up starting a support case (#281136500) after I tried all of your suggestions and was still getting the errors. Support went through the steps you suggested also; we even tried removing the Exchange Agent and reinstalling it and still no luck. They haven't come up with a solution yet and are going to keep working on it.......
As near as I can tell the problems started the day Hot Fix 4 & 5 were applied, but in the time since then I have somehow managed to get one or two good Exchange backups, but the rest fail at the very end. Is there a way to increase the logging level so we can better see what and where it fails a little better?
Joe.