The relay thing would suggest that it statically fails every other time? Switching it with another is a good & cheap test. Maybe the fuel pump is not delivering enough pressure on the first try. Remember the automatic shutdown relay will cut the power to the fuel pump relay after three seconds. Then at the second attempt, it fires up. Maybe it is a sign that the pump is tried? The only way to eliminate the fuel pump as the culprit, is to measure the pressure at the rail.
94 Black Laredo 4-Liter with QuadraTrac (42RE trans & NP249 TC) 200,000 + miles purchased new
88 Cherokee 2-door with 5speed manual 139K miles(deceased) purchased new