This is a weak spot in the native Cisco solution portfolio. I'll try to give one option but hopefully others will chime in with something more clever.
The MediaSense product can record trunk-side from Cisco CUBE which allows for device-agnostic recording; however, that only works if you're not concerned about internal calls to/from the analog phones (i.e. just to/from the PSTN). Getting the last part seems to require old fashioned SPAN recording to a capture server of a third party. This can get dicey though because most of the third-party recording vendors manually decipher the SCCP packets to figure out the calling/called party information. Be sure to ask them whether SCCP- or MGCP-controlled gateways are supported.
Please remember to rate helpful responses and identify helpful or correct answers.