There is no single/simple answer to this question, as every bank (and card vendor) uses different measures for anti-fraud. However I can provide some general hints and tips...
The first thing you can do to help reduce the chances of issues like this is to use the same card to book your flights to the foreign country as you use for other charges in that country. When you book flights, the card issuer is provided with details of the flights you've booked, including destination and dates of the flights. Most card providers will use these details as inputs to their anti-fraud systems - so when they see a charge for a hotel and a restaurant from the same city (or at least, country) that they know you have booked air travel to it's seen as lower risk than if they didn't have the record of the flights.
Next, especially if you can't use the same card for your flights, notify your credit card company that you are travelling. As you've stated, many companies have made this more difficult than it used to be, but most will still have a way to do so if you can get in contact with the right people. Check the website and app for the card and see if you can find anything there - for example, one of my credit cards has this available as an option in their app only, whilst another has it on both their website and app, but in both cases you need to go digging through the menus to find it.
If you can't find it in their mobile app or website, try calling and asking to speak to the fraud department if the normal operators claim it's not available as an option.
When you arrive in a new country/region, open your banks mobile app and login. Ideally do this whilst connected to Wifi rather than a roaming mobile connection, and if your banks app requests it, allow location access. At least one bank uses your location from their app as an indication that you are in a country/region.
Where possible, use either the Chip on the card or Contactless payments (PayWave, etc) rather than swiping the magnetic stripe or simply using the card number. In practice you often won't have the option of which mechanism to use, but the security involved is higher when using the Chip or Contactless so there is a lower chance of the transaction being marked as fraud. The act of having a Chip or Contactless payment in the country will also give your bank a clear indication that you are in that country - reducing the chances of future transactions being declined.
Change banks - especially to a larger bank! You commented that one of your banks had stated that "VISA is handling this", and this can actually be true. Many smaller banks/credit unions simply outsource their card management/fraud detection to Visa, in which case they have less control over such events. Larger banks generally have far more control as whilst they still may rely on the card companies systems to some extent, much of the fraud detection/response is handled by the bank itself.
There's no guarantee that following any or all of these will work every time, but at best they will reduce the chances of having a problem. Having a working mobile service for the number your credit card company has to contact you when you travel (relatively easy now days with wifi calling/eSIMs/etc) will also make handing the issues easier if/when they do occur - not just for the current transaction but also for any future transactions in the same country.
Personally I travel extensively, all around the world, and the only time I've ever had an issue with a transaction being (incorrectly) detected as fraud was at a gas station in the US (in a different state to where I live). However every single flight I book is done using the same credit card that I then use in-country (ie, the first point above!) - so my bank knows exactly which country (or at least, region) I'm in at all times.