Let's start with Java. With Java you have two options for licensing. First, you can use (possibly with your own modifications) the code from OpenJDK. Second, you can make a new implementation of Java, based on the Java specification.
There is no explicit patent license covering OpenJDK. OpenJDK is covered by GPLv2 and it is generally believed that when one licenses code under GPLv2 that license includes an implicit patent license. In 2004 Dan Ravicher, senior counsel for the Free Software Foundation, warned about the weak patent guarantees for BSD and GPL and recommended attaching patent grants.
This means the scope of the implicit patent license is unclear. On the one hand if all you do is use OpenJDK unmodified you should be completely covered. On the other hand if you made such extensive changes that it is no longer recognizable as Java and now infringes some Oracle non-Java patent, you would probably not be covered by the implicit license. Where exactly you cross the line from covered to uncovered is very fuzzy and unclear.
If you go with the option of making your own implementation, then there is an explicit patent license. That license covers you if you implement the complete specification, and if you do not make certain prohibited changes (adding fields and methods to the standard classes, putting new things in the standard namespaces, stuff like that), and if your implementation passes the "Technology Compatibility Kit".
The big problem with this is the TCK requirement. Sun could (and did) withhold access to the TCK from people who were doing things it did not like with Java. No TCK, no patent license for your implementation. In 2007 Geir Magnusson of Apache issued an open letter complaining about the Harmony project was unable to "acquire an acceptable license for the Java SE 5 technology compatibility kit."
Neither of the above options would work for Google. They couldn't go with the OpenJDK option for a couple of reasons. First, it is GPL. The handset makers and the carriers want to add proprietary features to distinguish themselves from their competitors, and Google felt Android would have a hard time getting accepted if it was under a license that did not allow this. Second, Java SE (which is what OpenJDK implements) is not really suitable for devices like phones. If Google morphed the code to be more like Java ME, they would be in that fuzzy area where no one would be sure whether or not the implicit patent license covers them.
Implementing their own Java following the Java SE specification, and then extending it (carefully avoiding making any changes to the parts that the patent license prohibits changing) might have worked--but they would still have the TCK problem. That path too would be a very rocky road, since Sun wanted Google to simply license Java ME.
Hence, Google went with using Java syntax and semantics, but not using the Java VM. No patent protection.
Now let's compare to .NET, and whether or not Google using Mono would have been safer. Microsoft's patent license for independent .NET implementations is the Microsoft Community Promise. Like Sun's patent license, it does require that you implement all mandatory parts of the specification. Unlike Sun's, there is no particular test that you are required to pass, and limitations on enhancing things. Implement the mandatory things in the spec--you are golden. (If you do enhance things, those enhancements won't be covered by the promise, of course, so some care is still required).
So right off the bat the patent situation is better--you don't have to get Microsoft's approval of your implementation in order to get your patent license. This fits in much better with what Google was trying to do.
Mono implements the mandatory parts of the spec, plus enhancements. Some of those enhancements are implementations of Microsoft .NET frameworks that are not part of the spec, such as WinForms. Those parts of Mono could have patent problems, so if Google had used Mono those would best be avoided.
Google might have still had to modify Mono to make it more suitable for small low-power devices like phones. That could take them outside of the ECMA/ISO spec, and into patent risks. However, there is a thing called the .NET Micro Framework from Microsoft, which kind of corresponds to Java ME. Note the license for .NET Micro Framework: Apache2. That license comes with an explicit patent grant. If Google had made Android based on a mix of Mono and code from .NET Micro Framework, they could likely have made it so all parts are covered against Microsoft patents--the Community Promise covering all the ECMA/ISO standard parts and the patent grant with the Apache2 licensing covering the enhancements for mobile.
What it really comes down to is that Microsoft followed the normal rules for opening up a technology. They submitted both the C# language and the .NET infrastructure to an independent standards body. They provided a patent license that covers implementation of those standards with no restrictions other than the common and normal restriction that you have to implement the required portions of the standard.
Sun did not follow the normal rules. They refused to submit Java to an independent standards body. They put strings on their patent license for the standard that effectively required you to get their approval of your implementation before you could get a license. Later, they did release OpenJDK under GPL, which was an improvement, but they did not accompany it with an explicit patent license, so no one knows just what you can do with OpenJDK (beyond using it unmodified) without running the risk of a patent suit from Sun/Oracle.
