I had the same and even lost a toe nail from running. I always had pain. When I was at the podiatrist for my nail, he says you have flat feet. For 3 or 4 years now, my comfort level has been so much better with a medically done orthotic insert.
I wish I did 20 years earlier.