After discovering that I was an over-pronater, I tried Superfeet insoles in my running shoes for a few years. Combined with the right shoes, they certainly helped to support my feet. However, niggling injuries including archilles tendonitis, eventually forced me to see a podiatrist who prescribed orthotics, which I've worn for the last 3 years. Originally I only wore them in my running shoes but soon started wearing them in my work and casual shoes as well.
I've tried them in cycling shoes but really don't see the point as its not so critical that my arches are as supported as when running. I've certainly not had any lower limb injuries that I could put down to cycling.
For the tendonitis, I assume you've tried the standard stretches such as eccentric heal raises?