"However the issue was very easy to solve: I used a thin needle to unblock the mic hole situated at the very bottom of the phone, next to the USB port. At first it felt like it wasn't a hole, as the needle didn't want to go in, but with a bit of gentle pressure it entered, and the problem disappear. I imagine dust or sand had blocked the hole and was muffling the sound."
After months of having everyone complain they couldn't hear me, this finally solved the issue. Indeed, you would think the microphone hole isn't actually a hole, until you take a needle and press gently so it goes into the hole. Voice quality was immediately back.
I should have known this: the microphone is next to the charger slot, and that too became completely clogged with dust a few months ago. I couldn't even charge the phone anymore! A toothpick brought out a relatively large amount of cloth particles (damn those jeans), and then everything worked fine again.
Thanks everyone!