How to automatically test the audio quality of a telephone line that randomly goes bad?
Pretty much every major (and minor) vendor of network testing hardware has products for something called VOIP (quality) (passive) monitoring/analytics or thereabout. These compute aggregate statistics on the quality of the conversations, among other things.  These usually don't run from your cell phone, but from a specialized routing/testing device. There's an ITU standard for VOIP passive monitoring called P.563 (this is the recommendation number) and also called 3SQM (the name of the algorithm), but it is not (yet) widely used by testing equipment manufacturers, and has been the subject of some criticism, e.g. [1][2]. So it's a bit of a wild west out there with respect to product features etc. for passive monitoring of VOIP quality.

I'm not endorsing any of these products, but here some examples:


http://www.gl.com/packetprobe.html
https://www.netiq.com/solutions/unified-communications-voip/voip-quality.html
https://www.sevone.com/supported-technologies/voip-monitoring
http://www.wildpackets.com/products/omnipeek_network_analyzer/voip_monitoring


You might be able to find some free software that does something similar, although you'd still need trunk-router-grade hardware to run it on. I was only able to turn up some 3SQM non-free software, which requires conversations to have been recorded by other means. There is a free piece of software called http://sourceforge.net/projects/voipmonitor/ but this does not do conversation-level quality analysis, but only testing for bulk suitability of the IP link to carry VOIP (ITU G.107). But you can probably at least use it to record conversations.

ITU has also put out a VOIP active conversation quality testing standard called PESQ and this is widely used by (active) testing products, but these inject a reference signal at one end and you don't seem to want that.

So the above generally covers "give me a way for me to automatically test a phone line audio quality". However, for your specific problem "the audio quality suddenly deteriorates and the outside party cannot hear us unless we talk very loudly", the issue may not even be (automatically) testable only from your side... If the packets leave your site unmolested but get messed up (volume-wise) by your provider/carrier or by some of their peers (probably not all), there would no way to establish that by just looking at packets on your end. You'd have to record/monitor the conversation from the other end to apply 3SQM to it.

My experience with cheap VOIP providers is that when they have (intermittent) quality problems the contracts/SLAs are harder to enforce than they are to terminate.