What is the name of your state (only U.S. law)? California.
If a company (in or out side of California) gives me a recording saying "This call may be recorded for customer service reasons" does this give me permission to also record the call without informing them?
If you continue with the call, the company has YOUR consent to record. You, in turn, need THEIR consent to record. You should inform them of your intent to record the call. They, then, have the same opportunity to stop the call or hang up on you as you have been given with their notice to you.
Because states have different consent laws, it is important to give notice whenever you intend to record a call.