If say HTC tried to enforce such conditions, they'd have little leverage because their devices are practically Android-running commodities. If HTC threatened to walk away from a carrier, it likely wouldn't hurt the carrier that much.
Since Apple's the only iOS device vendor, they have a bit more leverage over carriers.
Alternatively, they could team up with the other manufacturers and boycott carriers which refuse to sell their phones as-is. But they simply don't seem to care about their end-users as much as the carriers (and neither does Google apparently).
edit: spelling.
There's that, but it won't be too long before someone else releases The Hot New Android Phone. (Which might not live up to the hype, but it'll take the spotlight off the unavailable phone for a while.)
"This is exactly how Apple gained that leverage."
See above. The only company releasing Hot New Apple Phones is Apple.