These problems we are discussing are difficult. The somewhat obvious part is that I think in the end no single solution will be the best. 

Using a phone based solution is scary. I cannot understand why one would want to base their security on a transient and expensive device. Such devices are easily lost, easily damaged, and as crackers are discovering, breakable, just like any other software based system. These same reasons are why I believe "fobs," "tokens" or whatever you want to call them, are also not an optimal solution. However, unlike phones, they are inexpensive, disabled with minimal pain/inconvenience as compared to wiping a phone, and although potential targets for theft, not as big of a target as a much more expensive devices like phones. Likely fob thieves would know what they are doing (which is scary in itself), but they are most likely less numerous than would-be phone thieves.

The primary concerns I have about any system relate to how easy is to "rebase" aspects of the solution when different pieces are compromised; how expensive is the solution in terms of total cost expressed in dollars (new phone or token), time (administrative, transit, etc.) and resources (recreating the environment from scratch). Some of the suggested solutions rely on third parties so minimizing these dependencies when possible is probably a good idea. What happens if Oracle succeeds and Android is hosed in a few years (highly unlikely but possible)? What happens when YubiCo dissolves? What happens when Google pulls support for their OTP system (again unlikely, but possible)? What happens when solution x is compromised like the recent RSA breaches?

We obviously cannot predict the future, so I guess I'm wondering what matters the most to those who will actively be using the solution? Like Seth, and other mention, what groups are we covering? and what can we require of each of those groups? Is it fair to say if you want to be an admin you have to have the dough to pay for a phone and pay for a service plan? I don't know, but it will shape the demographic in certain, and possibly, unfortunate ways.

I also had a discussion with a friend who does a lot of reverse engineering. He mentioned the YubiKey hardware is trivial and that it would probably be more difficult to reverse engineer the algorithms involved in generating the OTP.

-- Take care! -Adam