I got another note on this from the server team. Apparently the Ubuntu LTS release (that 1/3 of the internet runs on) comes packaged with the older version of ffmpeg that doesn’t work with that codec. So, don’t be surprised when you struggle to record audio from iOS for the next year.
Having a similar issue with Safari on Mac 12.6.3. Audio from Chrome can be submitted without issue, as long as it is saved first. If I transmit the the blob directly via my Flask app, I get the Invalid file format regardless of whether I use Chrome or Safari. Taking my app to Windows to see if the issue persists.