It may be different form state to state, but i recall once being told by someone who should know that if one side says they may record the conversation, the other side can too without even mentioning it.
Some states don't require any notification.
Some states allow that if one party is recording, with notification, than the other party may as well without notification.
Some states require both parties to disclose, and agree, that they are recording each other.
As a customer when I call a company and they tell me they may record me I have the option to continue the call, which is an approval, or I can have the option to disconnect the call. If I choose to disconnect the call then I must use another form of contact.
Employees only have the rights that the company affords them in terms of not being recorded. Most customer service call centers will have policies that allow them to be recorded because there shouldn't be anything to worry about. If the agent does their job properly then there's not an issue. If not however then you get this:
That is the extreme and not the norm or we would see more posting like this.