Can you check the lines with a test set when the customer is having problems? That would eliminate a problem with the telco.
I know this will sound crazy, but I have had a few customers complain that callers on the far end cannot hear them. I would troubleshoot the problem like you did only to see how the customer was holding the phone. They were using their shoulder to support the phone, without using their hands, and this caused the mouthpiece on the handset to actually be under their chin. As soon as I showed them how they should hold the phone, the problem went away.
