I'll second (third) the vote for the furnace exhaust being part of the problem (although it might not explain why spotlights on opposite sides of the house come on at the same time).
However, I'll also add that a time-sensitive issue (problem is at night, not during the day) is likely another clue. Some here may remember I had a similar issue a few years ago, in which some of my switches would not respond at all at night. In that case, it was a noisy CFL bulb on my neighbor's front porch (only on at night) that was interfering with my system.
There are a few things you can try to narrow it down:
1. change the housecode/unit codes of the two affected units - see if the problem happens on other codes as well.
2. if the "universal remote" can send a code that turns off the lights (even if it is an "all units off" code), then at least *some* commands are getting through to those lights. Putting them on a different housecode would allow you to still turn them off that way without turning everything else off at the same time (the "All units off" command is housecode-specific).
3. Look around your house for anything else that would only be on at night (outdoor lights - certain indoor lights, cell phone chargers, computers, TV, etc). Are any of those things on more when it is colder outside (an electric space heater, perhaps)? Do you have any CFL light bulbs? Might any of them be starting to go bad (put your ear up close - a few inches away - do you hear a buzzing noise)?
4. You said that the units turn on about 30 seconds after the furnace turns on. You didn't mention the type of furnace you have, but I know that my gas furnace has several stages to the cycle - first the induction blower comes on for about 30 seconds, while the ignitor heats up. Next, the gas valves open, and the flames come on to warm up the heat exchanger. That's another 30 seconds or so. Finally, the main blower comes on to move air through the furnace. Depending on the cycle of your furnace, it may be the blower motor (motors create noise) that is triggering the lights. However, since you said it only happens when it is real cold outside - that might not be it at all.
5. You might try re-adjusting the motion sensors so they can't see the exhaust from the furnace (going back to the theory that Brian and Dave started). Do you have any indoor motion sensors that might be triggering the outdoor motion lights?