First, the law you are referring to is the Wiretapping law, and it varies from state to state. There is also a Federal Wiretapping law and that may override certain state laws or portions thereof. As for what you said...
WRONG... In some states it's a single party notification state, but in other's ALL parties must be notified. For instance, in New Jersey, I could record a call even if the other party didn't know, because "I know". However, in PA, I would be breaking the law to record a phone call unless I first asked the other party if they gave authorization, or at least notified them that I intended to record the call and gave them the option to say no. You need to check with your state's laws. Also I can't be sure, but it may be illegal to record a conversation with someone in a state that requires all parties to be notified, even if you are in a state that only requires one party to be notified, so in that example, someone living in New Jersey may be breaking the Pennsylvania Wiretapping law if they record someone calling them from PA and don't notify.
Why else do you think that you hear that notification on most customer service lines that says "This call may be recorded for quality assurance and training purposes."?
