Done all the above mentioned stuff.  All of it helped, but the real long term solution for me was getting a pair of prescription custom made orthopedic inserts.

They cost way too much, they're a PITA at times, but they made all the difference in the world.