How to prevent the Mail app from restoring its previous state?
I finally fixed the issue without data loss. Here is what I did:


Created a backup from the iPhone while the Mail app was still broken
Run Restore iPhone... within iTunes (I tried Restore Backup... which did not fix the issue)
After the iPhone was reset to its factory defaults I set it up using the backup I did in 1.