When I started working at my hometown radio station in the early ’70’s, recorded phone calls included a “beep” every 10 or 15 seconds, to let the person on the other end of the call know it was being recorded. Not sure when that stopped but for a long time we made sure we recorded the permission of the person being recorded. As for the audio quality of the calls? Think transmission from Apollo 13.
The most recent update to iOS includes the ability to easily record a phone call… and gives you an automatic transcription of the call.