That is correct - it is the car, not the gas (and not just the engine, either).
Oxygenated fuels have slightly less energy content, maybe half a percent to two percent; don't remember exactly. Not enough to make a large difference in mileage.
If you're not going from oxygenated to regular blend and back each year, then you're talking about a "winter blend" that has more highly volatile components to ease cold starting, but essentially the same energy content. No difference in mileage.
But your transaxle is harder to turn, your tires don't want to roll, the air itself is denser and harder for the car to push through, and yes your engine is spending much more time in warm-up with less efficient thermal performance and enriched fuel mixture. It all adds up.
Sorry, it's just basic physics. There's not much you can do about it.
- Glenn