the android/iphone example is a good one, but I don't think Android tries to be an iphone killer. It's a phone with it's own values. It's about choice and open-source, whereas the Iphone is about closed-source, proprietary code and a closed ecosystem. This is probebly a major reason why Android is taking marketshares. Google has different values than Apple, and it shows in Android. It has a different soul.
You mean like an Altavista killer, MySpace killer, or Blockbuster killer? Companies fail. Just because Apple is hot right now does not mean that it is immune to this fact. It probably won't happen six months after the ipad's release, but like everything else, something new will take its place.
Google wasn't an attempt to cash in on any kind of "search engine market", it was an attempt to remedy one of the biggest weaknesses of contemporary search engines: how to usefully rank a now-sufficient number of results.
Facebook wasn't intended to kill MySpace - it was intended to be better for a certain category of potential MySpace users: students. Initially, it was only marketed and available to them, and it was only after it had completely taken over that market that it was able to start seriously taking on MySpace.
Netflix could be said to have been aimed squarely at Blockbuster, but it's major tradeoffs of long wait times and a subscription model versus Blockbuster's same-day service and pay-as-you-go model made Netflix risky enough that nobody could have reasonably stated at the beginning that it stood a good chance of completely killing blockbuster so quickly.
Besides, none of the x-killers we see coming out these days are ever as drastically different as netflix was from Blockbuster; they're usually cheap knockoffs or more expensive versions afflicted by feature creep.