These apps are not recording Phone.app calls from the device. Think of it like Skype or a similar service for your computer. Although your computer cannot make calls, services can use VOIP (Voice Over IP) to send audio data to a server. The same thing is happening with these App Store apps.
- A user downloads a call recording app on the App Store.
- The user makes a phone call to someone from WITHIN THE APP THEY DOWNLOADED.
- The app starts sending voice data to the server and THE SERVER proxies the call to the destination number. You will notice that the interface for the "end call" button and dial pad are different, this is because Phone.app is not being used.
Now that the app is just sending it's own audio data, it has access to and can record it.
The open source application, siphon, is a great example of how VOIP can be implemented using Objective-C in an iOS app.