I went to the Genius Bar on Feb 20, 2014 in Raleigh, NC for this issue.
Of course, they've never heard of that happening before. So my genius stuck to the script. Here's the rest of what he said:
It's 100% not a hardware problem since it happens intermittently.
There's a 10% chance it's a software problem. Said with a dismissive shrug.
He *so!* *badly!* wanted to tell me it was my carrier, but I've hard two carriers and a Verizon Network Extender that have made no difference.
So he reset it to factory settings and that's all that Apple could do for me. He said that if that didn't fix it, that yeah, it was some problem with the phone (er, 3 phones in my case) and I should probably find a different type of phone. i.e. non-Apple.
So they don't like it at Apple when you point out that their product doesn't work and they don't have a solution.
I did have some improvement with the recommendations in this thread to shut off noise reduction and tape over the back mic. But I'm taking my third iPhone 5s back for a refund. I don't think $200 2014 technology should rely on tape to work just so-so.
Pay attention to this issue, Apple.