After spending a few days dealing with this problem, I have a pretty solid theory, as well as a solution.
My theory is that everyone has this problem has a nice, tight case, like an otterbox. This is causing SOMETHING that is creating this problem. My guess is either that dirt is getting stuck in the headphones jack or speaker or volume button area or something that is causing this. Or perhaps the case is getting mis-aligned and pushing on a button or something.
I believe this to be true for a few reasons. One, this would explain why factory resets do not fix the problem. Two, the fact that people who do things like "bend" their phones, blow into the speakers, etc, just proves that it's hardware related. Of course that doesn't explain why restarting it usually helps for a while, so who knows.
My successful solution was to take off my case, clean it up, blow into the "holes", and carefully put it back together. It's been a couple days now and I think it worked!