tl;dr: Ambient air temperature should generally not interfere with engine efficiency or fuel consumption, but will affect overall power output.
Do not confuse efficiency with power output. These are two separate things. When your intake charge is more dense, you can throw more fuel at it and creates more power. (NOTE: The idea for the engine management system is to maintain a general 14.6:1 air to fuel ratio (also called stoichiometric or "stoic" for short). This is the so-called "perfect" mixture of air and fuel where all of the fuel is burned with no extra oxygen being left afterwards. Unfortunately, the stoic mixture is not usually obtained. This happens because of two problems which arise, both having to do with the amount of heat which is created during the combustion process. First, the hotter combustion can cause detonation. Second, above a combustion temperature of around 1700degF, nitrogen in the air which is brought into the engine (along with the oxygen -- air contains ~78% nitrogen and ~20% oxygen) and burns. This creates NO2 or Nitrogen Dioxide. This is a major air pollutant and was the primary cause of acid rain talked about in the 70's in California. It is also very bad for us to breath -- toxic in fact.)
The flip side of this is efficiency, which in the context of engines means getting more usable power from the same amount of fuel. Great strides have been made in the past couple of decades towards engine efficiency. One of the ways they have accomplished this is through turbo-charging. In simple terms, turbo-charging is a way of utilizing the heat energy otherwise discarded in exhaust process. The turbo is able to increase the air charge by using the pressure created from the exhaust gases, which allows the computer to throw more fuel at the intake charge, thus making more power. This could lead to a very large "other" discussion, so I'll leave it here. Needless to say, power is made more efficiently through this method than through normal aspiration and thus the engine can make more power with less fuel.
Another way to improve engine efficiency is to increase the compression ratio (CR) of the engine. A general rule of thumb for CR is, for every point of added CR your power output will raise by about 3%. If you are increasing power output without adding more fuel, this is increased efficiency.
A colder air charge going into the engine will be denser and contain more oxygen than it's warmer counterpart. You are still using more fuel to create more power, thus there is no added efficiency benefit.
While you suggested to not include a cold start-up, there is a reason you will not see better fuel consumption during this period. The reason is because the computer actually throws more fuel into the mix to provide for increased engine stability (help keep it running smoothly -- like a choke would on a carbureted engine) and to help the catalytic converter warm up quicker helping it reach peak efficiency faster.
Actually, combustion engines can be quite a bit more efficient if they can utilize the heat instead of radiating it. Remember that radiated heat is lost energy. If you can utilize the heat to produce more power or create the same power more efficiently, you're just better off all together.
What I'm talking about is a concept a guy by the name of Henry "Smokey" Yunick had mastered in the early 80's. He worked off of an idea which Ralph Johnson came up with in the early '50's while Ralph worked at GM. The idea of a hot air engine in which the air is heated to around 400degF and homogenized (blended very well) to a point where it would not have detonation. You can read the article, but the reason it is not around in vehicles today is two fold. First, they tried to make it into a bolt-on kit, but couldn't do so because it required upgraded parts for the pistons and rings, which is in effect not so much of a "bolt-on" kit and makes it a lot more expensive than the target prices they were shooting for. Secondly, Smokey unfortunately died some time back. Way too many of his secrets died with him as he kept the particulars in his head. This is truly sad, because he did some truly AWESOME work and had revolutionary inventions and ideas which died with him.
The hot air engine flies in the face of common thinking about cold air induction and your question. Common wisdom states that the colder the air going into the engine, the better the output. And this is basically true with (what we consider today) normal engines (Smokey's hot air engine being an outlier).