You don't even need Iridium, a shortwave radio transmitter will suffice.
I find conflicting information about the Air Asia flight, a Bloomberg article claims the plane wasn't equipped, other places claim it was, but the airline wasn't subscribing to the data it generated.
It's not clear at all whether this is related to the cost of the system itself however.
Just 10 bytes or so every 5-10 minutes.
And over land you can use cell phone tower, so smaller carriers (who don't go much over water) would not be impacted badly.
Actually over land you probably don't need anything at all, so this really would just impact those best able to handle the expense.
http://www.aireon.com/AboutAireon/AnIridiumInnovation
Replacing orbiting equipment takes time and money.
Nevertheless, I also wonder why this couldn't work and just send the data more frequently. I don't know anything about the GPS consumers connect to but if my TomTom can connect to a satellite in space and give me my location down to a few metres at a regular interval then why can't a plane do the same?
Even a few dozen bytes worth of data every minute about current position, heading, airspeed, heading and speed of the wind is enough to reduce this theoretical "huge distance" (that is much smaller than what people have to deal with without tracking data) to a relatively small cone that can be searched effectively.