When the engine is turning, it can't be the starter motor. I also don't think there's something wrong with the relay, this should cause problems when engine is warm AND cold.

Check engine temperature sensor first. If this is working correctly, you'll have to check the fuel pump itself. There's a valve on top of it which holds fuel pressure in the system.

When you turn your engine off, the fuel in the injection lines near to the engine get very hot, the fuel inside also. It's starting to build air bubbles inside so there's not enough pressure left to open the injectors...