In most states as long as someone is legally recording then anyone may do so. If they told you that they are recording for quality purposes then you can record it too.
Sure. But they also have the right to hangup (which is what the rep said he'd do). I believe the law is that you have to notify the other party that you are recording, otherwise it can't be used in court.