Some banks do actually send and then ask for a verification code over the phone. And it's legit!

They have multiple types of verification codes, like ones for wires and another verifying your identity if you call customer service.

Avoiding fraud is complicated already and will continue to be a problem forever. As people get better at identifying scams, the next one will emerge. As companies create new policies to avoid fraud, "jerk"s will figure out ways to manipulate it.

I'm not sure a long term solution exists.