Hey Thomas,
Went through my first bout with pf this year. Tried EVERYTHING for 5 months (stretching, night splints, taping, ice, IB, 4 different brands of new shoes, over the counter orthotics). Luckily, a good friend gave me advice that worked for him, and worked instantly for me.
Go to a good podiatrist or orthopedic doc - one that SPECIALIZES in sports injurie)s. Ask around and go to the best you can find. First, get a cortisone injection. They really suck, but it was the only thing that finally rid me of the chronic pain. Second, get good, custom orthotics. You have to get rid of the biomechanical problem that causes them (but even if you get rid of the biomechanics, you may still have long-term residual pain, thus the cortisone).
Here's the downside. You have to take AT LEAST one week off of running and cycling after the cortisone shot - there is a high incidence of complete tendon/ligament failure the first 48 hours after a shot. Just get the shot and take it easy. Also, you have to give yourself a week or 2 to get used to the orthotics, and if they bother you, then you MUST go back and get them adjusted. Be patient with them. The third drawback is the cost - probably a little over $100 for the shot, and probably about $400 for the orthotics (I know you can get them cheaper, but I'm not sure it's worth it). Both the shot and orthotics cost me about $150 after insurance - damn cheap considering I spent $55 on a night splint, $300 on new shoes I didn't like, and about $30 on tape, not to mention the time I spent icing/taping and the loss of stomach lining from the ibuprofen. The final drawback is that each orthotic is about 3 ounces heavier than a standard shoe insole, and they don't fit in racing flats very well. You'll feel like your heel is elevated too high initially, but you'll get used to it quick.
I had instant relief after the shot - pain was completely gone in about 4 days (it still hurts a little the first couple of days after. The problem has not returned since I got the orthotics. Don't wait. Call the doc today. I can't believe I waited 4 months to do it myself - dumb move on my part!