As far as I know, the payments are for Android-specific features that those devices use. I don't think it has ever been proven that Linux infringes Microsoft Patents. In fact Microsoft contributed code to Linux and continues to do so (81980085). If there are violations, the most serious are about some FAT/VFAT patents and the Linux developer community can come up with alternative filesystems on solid-state disks.
From http://money.cnn.com/magazines/fortune/fortune_archive/2007/...
<< But he does break down the total number allegedly violated - 235 - into categories. He says that the Linux kernel - the deepest layer of the free operating system, which interacts most directly with the computer hardware - violates 42 Microsoft patents. The Linux graphical user interfaces - essentially, the way design elements like menus and toolbars are set up - run afoul of another 65, he claims. The Open Office suite of programs, which is analogous to Microsoft Office, infringes 45 more. E-mail programs infringe 15, while other assorted FOSS programs allegedly transgress 68. >>
So who must they sue? Right now, I'm sure Microsoft enjoys being perceived as less lawsuit-happy than Apple.