Not necessarily. Imagine the following: my company doesn't record calls, but we say that we "may" record calls because we think it will convince callers to behave. My employees know that their call is not being recorded, and getting one party to consent to something we don't actually want to do is business as usual.

If this took place in a two-party consent state then your consent alone is not enough, you'd also need the caller's consent which my company doesn't have. If you were to record the call without letting the employee know beforehand, that recording would be illegal.

But the company has said that the call may be recorded.