As far as I can tell, Microsoft claims they have patents that cover technologies/algorithms in the Linux kernel. I've never heard them get more specific than that. They approach companies and request them to pay a licensing agreement (or come to a cross-licensing agreement if the company has patents they can use against MS). TomTom disregarded the threats and got sued over Fat32. I imagine Microsoft's patent portfolio is vast enough to find something that will stick most of the time so the threats aren't completely unfounded.
Here's a brief article on the Amazon licensing agreement:
While I'm unsure of the details, I recall that Microsoft claims that Linux infringes upon many of their patents (don't remember the exact number). Therefor it is not unlikely that they would license out those patents to other companies who are known to be large users of Linux. If the cost of licensing were less than the expected cost of litigation (to have the patents declared invalid or demonstrate non-infringement) or if the companies believe that the patents are valid and that Linux would be found to be infringing if it went to court[1], it would make economic sense to license them.
[1] Which could be unimaginably costly for Amazon, considering their cloud offerings. If Linux were found to be infringing upon Microsoft's patents and they managed to get an injunction to prevent Amazon from using products shown to infringe[2], that would completely shut down most of Amazon and most of the web that runs on S3 or AWS.
[2] I'm not a lawyer, just extrapolating from cases where companies have been forbidden to sell infringing products. I'm not sure if this could actually happen, but it's a scary thing to think about.
So if you refuse to play ball and pay the license fees, what's Microsoft going to do to stop you? They obviously won't want to take things to court, as that'll mean exposing exactly which patents of theirs are supposedly being infringed upon.
Here's a brief article on the Amazon licensing agreement:
http://www.zdnet.com/blog/microsoft/amazon-becomes-the-lates...