We have a Ford Escape (2005 V6) with approximately 125k on it. I have done most of the maintenance on it myself since we bought it at 90k and it has overall been a great vehicle.
The past two winters, I've noticed it's hard to start when it's cold (<40 degrees). Hard start meaning: Cranks for several seconds (3-5), and it seems 'labored' while cranking.
I run Valvoline 5w20 Synthetic in the motor, and it has a new battery (installed this past summer) which floats at 12.5 volts. Doesn't smoke, and I replaced spark plugs with NGK's at the same time as the battery..and also cleaned the TB. No engine lights, but admittedly have not scanned for codes which don't trip CE light.
Not familiar with the starter motors themselves...do they "get weak" over time and worse in the cold? I can't think of anything else that would be affected by colder weather. In warm weather it starts immediately, and runs well.
Edit:
Thanks for the suggestions, everyone. I am going to start with a scan this weekend, and barring that turning up anything definitive, I will test/replace the coolant temp sensor, and see if i can test the ignition coils (it's coil on plug)