Nope not confused. The Sun vs MS Java fight was a cluster of patents on both sides. Thus why a judge ruled that whilst Microsoft had violated it's license to java, it could develop a similar system, i.e .NET. While I have heard these rumors before, I can't find anything in the .NET framework or how it works to suggest that they licensed Java tech. Oracles patents in these areas are actually pretty Java specific, whilst Microsoft's patents for .NET are very broad. (like every MS patent)
The core of my belief is that Microsoft must only have something "on paper" if you will. It's something they are pretty sure will lead to a protracted legal battle so not even they actually want to go to court to enforce it, but it's enough to make companies pay. That's why I believe it's something abstract and only loosely connected to Microsoft's actual patents. And most other components of Android you could simple replace with other known non-infringing implementations, since Microsoft has also made these kinds of threats about Linux, these components are out there. But rewriting Davik is a much harder task without licensing tech from MS or Oracle.
I would imagine RIM licenses Java. Everyone sues them for anything so if Oracle hasn't filed, they are licensed.