Purely mental processes, e.g. mathematical equations, are not patentable. This point has been affirmed.
That being said, a software patent is not always purely a mental process, or necessarily analogous to one. I would wager that if you look at the claims of each of MS's patents, there will be something more than the relationship of one item to another, which is what I understand a mathematical equation to be. Any claim to such a relationship has been deemed not patentable subject matter. In my opinion, the Federal Circuit's "machine-or-transformation" test adequately addresses this issue, requiring that a claimed invention involve more than a trivial step being performed by a machine, or the transformation of an entity, something more than transistors changing state.
I say society gains from software patents exactly what it gains from patents in every other art; public disclosure and encouragement of research and development. You ask if Microsoft would have written any software if it did not have patent protection available to it. It seems likely the answer is yes. However, going back the decades of Microsoft's existence, looking at the enormous amount of resources Microsoft poured into R&D, it is far from obvious that MS would have developed many of the technologies it has developed to date.
First, if Samsung and Google are unable to challenge the validity of these patents, it is not for lack of resources. That seems to make it more likely that there is a lack of prior art raising a substantial new question of patentability, essentially meaning they cannot find prior art to challenge validity. If that is the case, then novelty/obviousness probably are not grounds for invalidity.
Second, I see no reason why the invention should not be patentable. The patent system is a trade-off of public disclosure of the invention in exchange for a grant of a limited monopoly. So, yes, it does present a monopoly; that is exactly what was intended. You say only Microsoft can resize text with handles, and that is bad because it is a feature everyone expects. I ask, why does everyone expect that feature? Is it because Microsoft included it in all of its products, making the feature a much desired one? If the invention truly was disclosed prior to Microsoft's filing for a patent, show me the prior art making that disclosure. If such a reference does not exist, do not waste your or my time saying it was obvious; that reeks of hindsight bias.
As to the J.K. Rowling, the works of authors are protected differently than the work of inventors for a variety of reasons. Needless to say, copyright protection affords less protection, but for a greater length of time. As to trademark protection, that too is a very different type of protection for a different length. I agree that the concept of a boy wizard story should not be patentable, and indeed it is not.
I disagree with your statement that we overrate the idea, at least as far as you seem to imply we undervalue the implementation. When you read through the claims of patents, you will find the implementation of the invention described by the title is much more often the patented invention. Indeed, this is something the Supreme Court has been grappling with in recent cases; abstract ideas should not be and are not patentable. Just see Bilski. A definitive test for patentable subject matter has not yet been crafted, but I think it would be throwing out the baby with the bath water to categorically exclude software from patent protection. Why should a concept, the product of significant investment and innovation, be excluded simply because it is executed within a digital framework?
The best things in life go on sale sooner or later.