Before Marshmallow (2015), recording phone calls was behind the same permission as recording the mic. This was obviously bad as voice calls are much more privacy sensitive than the mic. In Marshmallow, phone calls recording was updated to be guarded by a new permission, a system one, so only system application can access it.

Nevertheless, there were multiple ways to bypass the new system permission, which call recording apps made use to continue recording calls even without the system permission. Those ways were fixed one after the other as part of securing and refactors of the audio stack. The last such bug was fixed in Android 9.

Any OEM can bundle a call recording apps, it's just that many don't.

Does it mean if I had a rooted phone I could get the call recording working on latest Android?

I am still going with 2018 phone and it's a bit worn now. Only thing that stops me from buying a new phone is that missing feature and when I ask about call recording the sellers would say yes there are plenty of apps in Play Store, but they don't know these apps don't work. I don't know how reliably I can find out if the phone at least has a manufacturer's call recording app.

Some phone hardware architecture can't let the AP (the Processor running Android) access the call audio (because the audio stream is routed directly from the mic/speaker to the modem). On those no amount of root hacking will allow you to record calls. Nevertheless this is rare nowadays where all the audio goes through an ADSP connected to the AP.

Your best bet is to find a phone manufacturer/vendor that advertise call recording support. Alternatively search on call recording website like [1] which phone they support rooted. [1] https://www.boldbeast.com/android/call_recorder.html

On the Boldbeast forum there are some phones listed that work, but it seems like this depends on the region the phone comes from. I think I will have to buy a phone, see if it works and if not return. Rinse and repeat... What a nightmare.