This is a peculiar problem with the Samsung M51. It appears to be a software issue related to some settings in the Phone app.
When calling others using the handset, they cannot hear me the first time. I disconnect and call them up again, and they can hear me very well. Also, when they call me, I could hear them and they could hear me well.
To fix this, I took a backup and did a factory reset. So classic Windows trick of formatting / reset applies to phones now :-).