Once again 4 Jaw Chuck is correct. The link below will run you through a comparison of Grade 5 versus Grade 8 as related to shear.
Grade 5 vesus Grade 8
Since it would be nearly impossible to fatigue this fastener in 26,000 miles under normal circumstances (unless you spent all your time off road), I would look to installation technique, proper design of bolt size versus grade and/or manufacturing flaw in the original bolt. What's most interesting is that you stated it had failed through 90% of the cross section sometime earlier based upon rust in the shear area.
Another comment that troubles me was "the fracture would be indicative of over torque". This is a common misconception. Fatigue failures are more commonly accelerated by under torque.
The most telling info in the "fix" was not a properly heat treated Grade 5 bolt direct replacement, but was a properly heat treated Grade 5 bolt 1/8" larger in diameter.
I don't know the circumstances of this failure and therefore won't comment, but the misinformation on different grade bolts in shear does a disservice to the rodding community. Everything else being equal, I'll bet my life on a Grade 8 bolt over a Grade 5 bolt any day.