My phone over the last few weeks has exhibited behaviour where the remote party cannot hear me, whether I make or receive the call. Very frustrating. I tried rebooting, updating to 4.3.5, doing a full restore (set up as new), and still callers could not hear me.
I ended up taking it to the Apple Store yesterday, where a Genius looked at it. He tested the voice memos app to be sure that the Mic itself was working, then declared that it was a hardware failure of the noise cancellation mic. Because I'm an early adopter (day 1 phone), I was 94 days out of warranty, and therefore all he could do for me would be a $199 replacement.
I told him that that was a shame as I can't see spending $199 on a replacement iPhone 4 when my upgrade is ready for AT&T and I'll be getting [whatever Apple releases], probably on launch day.
Once I got home, i took the two screws out of the bottom of the phone, took the back off, and went at the noise cancellation mic with some compressed air. [YMMV, No warranty, etc.] I figured I didn't have anything to lose - worst case scenario something breaks can callers can't hear me.
To my surprise, when I made a test call after putting the back back on, callers heard me. It's been working fine since then, so hopefully whatever was causing the issue has been rectified.
If not, at least I will be getting a new iPhone next month and I can start the cycle anew.