I do not think its a good strategy to attempt repair of a problem according to a list priortized solely by cost. Based on the description you have given here the list would be lengthy. What if it the last item on the list that finally fixes it? It is better to gather all available facts, perform appropriate tests, diagnose the problem and repair. This is especially important with an intermittent problem such as yours. The basic facts and full description of the symptoms and history must come from you, a mechanic cannot know without your help.

A new battery suggests it is an electrical problem, does it fail to crank?
A new cold temp sensor (engine coolant temp sensor?) suggests that it is cranking fine but fails to fire.
Can you state what other tests and services were performed by these mechanics?
Detailed observations by you during the no start condition are especially important.
Does the starter crank the engine at normal speed?
Do you hear/feel it attempting to fire?
Can you hear the fuel pumps?
Does it run normally right after it starts?
What preventive maintenance has been performed recently?
Once warmed up how does it perform?

Post back, it is likely this can be worked through.
--
David Hunter