^^^ Thank you, thank you, thank you!

I scoured the web, found about 200 pages all saying the same, hanged the settings accordingly, rebooted... nothing.
Then I noticed the MMS settings have a menu! With a single menu entry, "Reset to default". That did the trick.

The problem must have been introduced when I wiped the device and perhaps did not restore it properly. But it works now, thanks to YOU!

(Now I have only one problem left, "File type 'audio/AMR' is not supported". But I can live with that )