If you call a number, and you get a message like "calls recorded" before the rep answers, you can record that call because they are. They have given you notice and that notice also goes for them.
Just be sure you record the message "calls recorded" and you do not have to notify the rep after that, they know their calls are recorded.