Only the ones bough from Googles Android Market
Thats interesting then. Setting up an Android market with Bitcoin is a great idea. Does Android have any other limitation in the software that can be installed?
Not really, you only need to go to configurations and check "allow installation of non-market applications". I think some US-carriers block that feature on some phones though, but not sure how common that is since I'm from Europe. In that case you would have to root which only a fraction of the users will do. Outside US most phones are unlocked in that respect.
Google Market has automatic updates which are very convenient, so that would be a nice feat.
If we convince only a few % av the devs to jump on it would still be huge. And it could probably be done, I think app developers in general are the type of people that think Bitcoin is a pretty cool idea.