After years of flying, I had to find a solution for this problem.
I had shoes custom made by an orthopedist technician, with their own custom made insoles (molded on my feet). After a trip or two I also had a layer of a special soft rubber applied on top of my insoles, to make it softer. Problem solved, but the downside is that it was extremely expensive (but still worth it for me).