MS maintains that Linux kernel violates its patents, and sues anyone who makes enough money with a product using Linux (e.g., TomTom [1]).
MS likes to refer to "235 patents" that Linux allegedly violates, but they aren't forthcoming with what the specific violations are. That said, they do have some fairly ridiculous patents under their belts, (like the FAT filesystem [2]), so they could probably dredge something up.
With Android more specifically, there is also ActiveSync (Exchange's protocol).