I've gone through similar, and understand your frustration. There are a lot of potential causes of foot pain, and a lot of types of deformed feet, so my experience (or anyone else's) may not help much. Personally I have semi-flat feet, and most of my pain was coming from the balls of my foot. For what it's worth, I went from not being able to make it through a run without stopping multiple times due to foot pain, to having slight discomfort but it not really being an issue. Cat tracks on my toe side were pure agony. After doing all of the following, some combination of this led to improvement:
Superfeet inserts didn't help at all, tried them briefly, got rid of them.
Had custom footbeds made at a local ski shop. Cost was about $160, and I stood in some things I would describe as plastic memory foam. They used the impression to put a fiberglass insert into and take the shape. Tried them for one day, and it seemed like there may have been some improvement, but not nearly enough. Still couldn't get through runs without pain.
Returned to the shop, they shaved the footbeds a bit, and said the fronts of them seemed a little wrong. They also did some slight modifications to my boots in areas that I reported pressure.
In the same visit, I bought some new bindings that had some padding under the foot (I kinda doubt this was the issue, but mine were old/cheap anyway). People seemed to suggest bindings a lot, but I really doubt this is a major factor in cases like us, because you mention having pain in other activities such as working out.
Since then, I also have been take Ibuprofen before my first run. This helps with inflammation/swelling, but you should be aware of the health risks of doing this habitually: For Athletes, Risks From Ibuprofen Use - NYTimes.com
The last few times out with the above formula let me have a good time. Another factor could have been just breaking my feet in more as well.
tl;dr - you're probably going to need to find a bootfitter that you can make multiple visits to, and who can make you footbeds