Cranks too long to start hot,and smell fuel when it does,

Hot starts fail.
ever do a tune up, spark parts? filters?
does it start backup if you WOT crank it
WOT -= wide open throttle or as some say flooring the gas pedal
and crank it. (the trick is it cuts fuel fully to clear the flood)
this clears flooding, (on all EFI cars made)
or test #1 , crank with just 5% added throttle this trick
adds air to hide bad IAC valve. and engine starts. (tricks/skills/ASE magic)\what eva.
but may stall if you lift the right foot, does it? hot?
test 3. will it start up with sprayed, instant start in a can?
hot? at air cleaner intake,
run for 3seconds and stall.
if yes fueling is wrong, (as in none)
if NO, spark is dead or weak

no car told maker or model or engine size.
there are lots causes that, hard starts
if spark good and strong and even HV spark wire sets fresh.
the short list.

1. bad fuel
2. too much fuel cranked and floods
3. IAC bad, idle air valve stuck and wants to flood cold.
4. cold idle is the big clue, where too low. IAC failing
5. EGR sticking open at idle. possible.
6. if you press gas Pedal, at 5% (about) and starts easy and likes that until it worms up that means the IAC is dead.
7. I stop here lots more, no car told.

all cars modern EFI is it EFI> have IAC and ISC valves 1 or both.
and if stuck idle fails. hot or cold.
no car told why post like that 100 year of cars and 10,000 engines.
????

Have you replaced the coil?

change your MAP sensor and clean the IAC valve

Good spark, them it must be fuel related. Smell any fuel coming from the exhaust. Check relays. Cracked solder joints may be contracting when cold. Hot wire fuel pump and try to start.

There are several things that few people know about starting cars in cold weather. 1. Check your battery to make sure it is not rusted, leaking, and has a charge 2. Jump start your battery with another car, even if you believe the battery is good, this often times will still start your car. 3. If your engine is cold, and you have an older car, ensure to get your fuel lines to the engine flushed or have fuel injection service performed 4. The engine tends to warp the same way wood does during the extreme cold, do not be afraid to continue trying to warm up the engine by constant cranks with it is cold out. Your not going to hurt the car, the worse that could happen is too much fuel will enter the carborator and cause flooding in the system to occur. Wait 20 minutes if this happens and start to crank again 5. Bad spark plugs are a major reason why many cars take a very long time to start 6. Please have your spark plugs removed and exchanged for new ones. Over time, spark plugs become fowled and prevent the car from starting even thou you hear cranking!!!

Not to put firestone down but how intricate was this diagnostic that they preformed? It sounds like they just plugged into the OBD2 port and looked for any codes in the history.
You may be right, it may have to do with temperature. But I'm thinking more in the respect of a faulty sensor that is changing with temperature. That is, if it has to do with that.
The other thing is the fuel-pump. Has it been tested?
If possible, When this no start situation occurs, investigate it. Find out if you have a no-spark or no-fuel situation.

I would suspect fautly spark plugs.

It may be due to a failed/faulty fuel pressure regulator. I had this problem: easy start when cold, hard starting when warm/hot, and rotten egg smell from exhaust when warm/hot. My mechanic diagnosed a failed/faulty fuel pressure regulator, replaced it, and now the problems (warm hard start, smell) are gone. I have a '92 GT with L4 engine.

Check the fuel pressure when the vehicle is cold and compare it with when it's hot.Also check the fuel return dump valve , that this isn't returning too much fuel.