I know that you are required to notify someone if you are recording a phone conversation, but do you have to do so if that person himself has already notified you that you are being recorded (as most customer service departments do, for example)?
Also, are you committing any crime if you say that a conversation is being recorded but it really isn’t?
Most states allow recording of conversations without notice, these are one party states. Only 12 states require permission of both parties. It is illegal in all states to record a conversation you are not a party. As far as the legalty of not recording and saying you are, I could find nothing in the link below.
I regard the phrase “This call may be recorded or monitored for the purpose of quality assurance” as giving me permission to record or monitor the call. If they intended another meaning they should have been more specific.
Cute, but good luck with that in court. 
Why?
I’m the organizer for the local copwatch program, so I can tell you about what Kanadian law has to say on the subject, anyway. It’s legal to record a conversation as long as at least one party is aware it’s being made. However, for it to be admissible in court, all parties must be aware that it’s being made, which is why we always inform police that they are being recorded.