You've pretty much got everything you need to answer your own question. Unfortunately this isn't a new problem either. Here's an article from the BBC in 2012 that describes your exact problem, questions, and concerns:
http://www.bbc.com/news/uk-19677434
This article mirrors a lot of your same thoughts and has the same conclusion hiding between the lines: someone who calls you and asks you to verify your identity is doing things completely backwards. It absolutely trains people to have have habits (my bank says they called - let me give away my information) that make them more vulnerable to scammers in the future, and it's a poor way of doing business. Again, in the BBC article you get a clear impression of why the banks do it: it is a quicker and more cost-effective way of getting a hold of customers and stopping potential fraud early. On the face of it, that sounds like a good thing. However, as you point out, it will absolutely train people to have the wrong habits in the long-run, potentially increasing fraud.
It all boils down to a single unfortunate fact: just because banks handle our money doesn't mean that they are actually good at security or understand the broader ramifications of what they do. That fact is very obvious from the severe bungling that many banks still have in regards to passwords, as can be seen from any number of news stories (these are from 2016):
- https://threatpost.com/weak-bank-password-policies-leave-350-million-vulnerable-say-researchers/116574/
- Bad password policy at my bank
- https://www.securitymagazine.com/articles/86965-research-finds-bank-password-policies-often-weak
As I think you already understand, you can't just assume that these guys actually know what they are doing. So what should they be doing? In the end complicated problems like this will only be solved with a multi-faceted approach.
- Use an official app and to notify the customer through that. This actually has the best bet for quick responses. Unfortunately, there are probably a large number of customers that won't ever install the bank app which means that this can't be the only answer. Of course, you also have to make sure your app ecosystem is very secure: otherwise you just create a new avenue of attack for hackers. Moreover, you have to be extra vigilant against the potential dangers of stolen phones being a source of fraud.
- Calling people with an automated message and asking them to call you back on the number on the back of the card is probably the most effective all around option. It will reach the most people, and it will get them in the habit of the most secure method of contacting you. I would have the automated message say something like "please never give out personal information to unexpected callers who call you: always call the number on the back of your card if you have any problems". As you say, this gets people properly trained. However, there are some people who may ignore the message (I sometimes ignore phone numbers I don't recognize and I also don't have voicemail turned on).
- Text alerts are another good method of letting customers know there is a problem. Same thing: "We found suspicious activity, call the number on the back of your card ending in 1234".
- All of the above options still leave holes where the customers may not get back to the bank quickly. This is the banks biggest concern and why some banks (such as the ones in the BBC article) feel the need to send out automated calls in an insecure manner (i.e. asking you to verify yourself after they call you). Fraud that does not get resolved quickly costs the banks more money: there is a finite period of time when they can cancel the transaction before money is even sent, and if a card has been stolen the quicker they cancel it, the less fraud they have to deal with. Therefore, the bank needs to take action, and the sooner the better. As a result the best bet for a bank is a final step of freezing a card if fraud is suspected and a quick response isn't received from the customer. I've had this happen plenty of times: my card gets frozen because of suspected fraud, that forces me to call the bank, and then everything gets resolved. This is also an option that you have to use judiciously. People get irritated if you constantly freeze their cards for no good reason and ask them to call you to get it unfrozen.
Again, these aren't meant to be competing options: a banks best bet is to reach out to the customer immediately in a few different ways and establish communication over a secure channel (i.e. a well secured app or by calling the bank directly). Then you can ask them to verify themselves without worry, and you've taught them proper security best-practices. This also isn't particularly hard to do, or expensive to setup. Unfortunately, I doubt many banks operate this way.
But what about ...
This is worth a mention. The answer I gave is very straight-forward and simple, and is basically just: contact customers via phone/app, have them call you, and then straighten it out. This is such a simple answer that it is almost silly. There are plenty more options that we could come up with. How about the bank verify itself via some pre-shared secret? How about using some sort of OTP scheme? What about some form of pre-shared private-key encryption scheme? (that last one is practically gibberish). There are probably lots of ideas people could come up with to let a bank verify itself to a customer to get the process rolling and not force the customer to call the bank back. The underlying problem with all of these though is that it relies upon the customer to be able to understand and follow whatever the method is successfully a high percentage of the time. That is never going to happen.
The reason we know it is never going to happen is because it's hard to get people to follow even the simplest of advice: "Don't give out personal information to unsolicited callers! Just call your bank directly" or more generally "Don't reuse your password on multiple websites!". Banks aren't bad at security because banks suck: they are bad at security because WE are bad at security. Banks are limited in their options by what they can actually get their customers to do, which is not necessarily much.