Q:

Hard cold starts only

98 Jeep Cherokee (XJ), I6, 173k mi
When trying to turn the cold engine over, I have to crank things for at least 3-5 seconds. In some cases it will not start on the first try. After starting it runs a bit rough for a few minutes.
I've suspected the fuel check valve going bad and have turned the key to on for 2-3 seconds, off for 2-3 seconds, 3 times before trying some cold starts and this makes no difference.
I've also checked the fuel pressure via the rail (within spec), and its ability to maintain the pressure over 15 minutes with no drop.
IAC operation has been checked as well.
Other info:

The tach needle wavers slightly when idling.
The exhaust always smells strong, but is clear.
The battery has been replaced with the last 3 months.
Distributor cap contacts have 1/8" notches.
Rotor shows no wear.
Plugs are 6 months old.

If the car's been recently shut off, it has no problems starting right up.
UPDATE: Before performing any service, I filled up with premium gas. Since, crank time was greatly reduced, and would always start on first try. I've since performed a seafoam induction service, throttle body cleaning and turn-over is now immediate. Long term testing of fuel pressure is next.
UPDATE: The fuel pressure check resulted in ~46 PSI initially. This dropped to 40 in an hour, and 34 after 5 hours. While The check valve is on its way out, I don't think it's the cause of the issues considering the flying box is still starting on the first try and immediately each time since the gas change and induction service. However, I'm still waiting until I'm through this tank of 93 octane with seafoam added.
LAST UPDATE: Refilling the tank with 89 octane a few days ago, I haven't had the issue again. Considering this and the induction service was performed before anything else, with immediate results, I feel it may have been this that fixed the issue. However, the seafoam gas additive may have cleaned the injectors some over the last few weeks. I'm unsure as to how the higher octane contributed, if at all. Perhaps its a red herring. I'll wait a few days before accepting an answer if anyone has comments. 

A:

I believe the key clue here is the fact the engine runs rough for a few minutes.
This tells me that the cold-start enrichment, where the air-fuel mixture entering the cylinders is slightly rich, isn't taking place.
You may be looking at partially clogged injectors causing this. The reason I think this is the cause is that you've ruled out fuel rail pressurization as an issue.
You might be able to get away with just running a bottle of fuel injector cleaner through the fuel tank. If that doesn't work the injectors may need to be taken out for more thorough conditioning.

A:

This may sound strange but try preforming an induction service. There is a condition that can sometimes occur where excessive carbon builds up on the intake valves. When carbon is cold it is porous and can absorb gasoline keeping it from getting into the cylinders. Eventually the carbon becomes saturated and fuel enters the cylinders. 
When the carbon gets hot it is no longer porous and while the engine is hot it starts just fine. 

