I have researched this to the best of my ability and I'm still coming up against some trouble. Let me thank everyone upfront for your help. I'll detail the situation as best as I can. If I miss anything I'm more than happy to go back and get the ...
I forgot to mention media:
The backups go to a Dell Powervault TL2000.
We have a Weekly Full and Daily Diff setup with media rotation rules set such that we keep a few weeks of backups hanging around.
I've seen some "suggestions" that the mailbox stores might be corrupt but I'm hoping that isn't the case. The small bit of science I'm using to support my hope is that my backups do work, currently my failures are only intermittent.