Did you replace the one-way valve (~$30) on the discharge side of the pump? You may need to hook a pressure gauge setup on the fuel system to check residual pressures at the time of the hard start, but it may be your fuel system leaking down. I've also seen fuel pumps that started fine after running, but wait about 10 minutes or more and the commutators will not allow motion or the bearings are seized enough to require multiple tries to engage the fuel pump. Make sure the fuel pump is cycling when you turn the key over, and cycle the key a few times to both listen for the fuel pump engage every time, and to pump the system up so it will start right away.

I also have seen the fuel injection coolant temp sensor (located on water pump, with big black snap-on plug) go bad and cause similar problems.

__________________
Don't ask me, I'm a shop-owner by default