When my starter failed, I tried my remote starter with no luck as I recalled you had mentioned this.
I believe the relay wear that's ultimately causing this, over time builds up corrosion/pitting on the contact surfaces such that it creates a high resistance surface that progressively increases in resistance until in no longer works. That mixed with cold weather, which has the effect of reducing battery voltage and current capability (potentially on a weaker battery), colludes to produce your non-start issue.
Why the remote start works...is particularly interesting. I tried it many times. I chalked it up to not opening up the door, lights/ecu's waking up, which leaves more battery electrons to overcome that contact resistance in the relay.
Just a theory.