"This call may be recorded for quality insurance purposes" - Can I record too?

Simple enough, in California at least. Have your recorder make a beep every 10 seconds on the line. That will satisfy the notification and consent issue. If the other party keeps the call active, it’s assumed their consent has been given. Banks operate in this manner on a daily basis.