If fuel pressure was normal, I don't know why the condition would be altered by re-seating the fuel pump relay. Maybe you need to verify if fuel pressure was in fact normal or not, but if it runs fine when driving - I don't think this is the issue. Those have an EKP relay and do not behave, or fail, like normal relays.

Camshaft position sensors will throw codes but will not prevent the engine from starting. Crankshaft position sensors will usually throw codes, but not always. If the crankshaft sensor is faulty, you will not have any tach signal when cranking.

I have never heard of a failing fuel pressure regulator causing issues only during cold starts. But again, if fuel pressure is ok, I don't know why this is a main consideration.



If fuel pressure is in fact OK as you say then you are going down the wrong path looking at fuel system related stuff.
Double check if fuel pressure since you dont sound confident in that but if is actually ok but if it is, look elsewhere. I start with the simple stuff in cases like this - make sure the battery connections are tight, engine ground strap secure, etc. Could also simply be a starter on it's way out - when those fail, they do often fail intermittently.