Can anybody explain how this was a hardware problem?

When you downloaded the firmware did you use the iPhone without restoring your backup user data? If you used a perfectly clean iPhone firmware, then I can't help you. If you were restoring user data from a backup after a firmware refresh then...

I had the same issue. I re-downloaded firmware and everything else you tried. But each time I had iTunes load my old user data. Finally, I just said forget it and did a sync/load from scratch without restoring my user data. Everything worked fine. After it worked, I tried restoring that backup/restore point - immediate crashes in mail again. That backup point was no good.

It seemed like a corruption in my user data/settings. And I still have no idea what it was... Other than my data restore point.