Let's assume everything you said except the conclusion is right (I disagree with almost all of it, but for the purposes of this discussion I'll put that aside since it's better argued in the fine legal briefs).
Why does fair use for interoperability require perfect interoperability? That seems like a totally unreasonable bar. It would mean that making some fraction of an API ridiculously complex to implement a way from stopping anyone from implementing the rest of it.
I'm not talking perfect interoperability - I believe that substitutability should be the bar.
Google produced something that is not substitutable in either direction, so what I perceive as the reasonable fair use argument cannot be used here.
What do you mean it's not substantial? People use the same java libraries on android and servers all the time, thanks to being able to use a shared standard library API (the supposedly copyrighted material in question in this case).
You seem to be arbitrarily setting the scope for substitutability to Java as a whole, but why? Why can't it be e.g. individual classes, or even methods on them? Two pieces of Java code pretty much never need the entirety of J2SE API to interact.
The destruction of interoperability wasn't the goal in mind with Android either. Java ME sucked, and SE is somehow even a worse fit for phones. The fundamental process model destroys battery life, hence the switch in Android to that model that'll shut the app down basically at any time and allow it to save state, so it can come back to where it was later. In addition to that, an IPC system was added (which basically doesn't exist in Java ME), and a bunch of support for devices that are only accessible in Java via 3rd party libraries anyway. Oh, and the lack of swing. But come on, even Eclipse doesn't use swing.
Why does fair use for interoperability require perfect interoperability? That seems like a totally unreasonable bar. It would mean that making some fraction of an API ridiculously complex to implement a way from stopping anyone from implementing the rest of it.