First obvious port of call is to replace the dock connector - however you've verified that from a hardware point the microphone works so I don't think this is your problem.
It sounds like the audio decoder. This is a fairly common problem with the 4 and 4S. Apples policy is to swap the phone out for a replacement but that's useless for phones over 12 months old.
If your iPhone is under 12 months old take it straight to your nearest apple store.
Symptoms are exactly as you've described. Sometimes the problem is intermittent whereby it will work for sometimes days without trouble but then will randomly mute for no apparent reason. It will then sometimes work from time to time but eventually getting worse and worse to the point that each and every call is the same.
Without some serious soldering skills your best off looking for someone to do it for you. I'm not aloud to advertise services on here but if you message me I can help. If not you please look for an experienced, reputable iPhone repair company - its not a simple repair.