So first off, Im not a mechanic.
A lot of people assume this is just normal, you have chased it the logical route, as most of us have.This includes many mechanics, ask me how I know.
If the pressure is holding (which sometimes it drops over time, so check that) then you are good on the fuel supply side.
The other side of this is electrical, which you have also looked at the starter so that should be good. Check a couple things, just as with the fuel pressure you need to check the electrical pressure (I know it sounds stupid so we can just call it amps then)
you need to check you batteries ability to cold crank. You need to check your battery connections to make sure they are not resisting during the very high but short momentary surge current that gets it going. You need to check the connections to the starter and the wires along all those paths. (you can use a voltmeter for all this as well as visual inspection)
I have found that the wires going to the starter are undersized and can eek out more current to the starter with a thicker wire. The current needed to get that big ass engine moving is quite a lot. If any one of these things are iffy, you will end up with your situation. I was in your situation for years literally, lol. Not an issue anymore, as I have also replaced all those items you suggested but also have a more powerful (cold cranking amps) battery and bigger connections and wires and now its good.
Just remember its about pressure to the system, any choke on that pressure will stall it. This means that as it sits, over time any of the components that can lose pressure will likely be your culprit. Check-valves, batteries, fuel lines, etc.