Early published occurrences of verb forms of 'misunderestimate'
Although George W. Bush is undoubtedly responsible for the proliferation of (usually sarcastic) use of misunderestimate from 2000 onward, he is certainly not responsible for the first occurrence of the word in print. That honor may go to the unnamed author of "American Diplomacy on the Bosphorus" in The Outlook (April 17, 1897), who writes (with no hint of sarcasm), as follows:
Unfortunately, it is rarely that the State Department and the Minister Resident are both alike firm and intelligent in Turkish affairs. One of the two is almost sure to misunderstand or misunderestimate the significance of a question at issue. Thanks to their lack of previous diplomatic experience, Secretary of State and Plenipotentiary both alike have to depend, in most cases, upon trusty subordinates, kept at the same post through successive administrations because of their mastery of the local routine and conditions—men, usually, of cautious and colorless natures, often of foreign birth and destitute of intelligent sympathy with American ways and ideas.
From "Is Preaching Passé?" in The Christian Century (July 1, 1920):
Dr. Lyman Abbott recently reviewed "Marse Henry's Autobiography" and quoted his advice to the ministry, which begins with Mr. Watterson's judgment that the pulpit has always been "the moral hope of the universe and the spiritual light of mankind." In one of his last sermons, Washington Gladden says: "I have never misunderestimated my function as a preacher. There is no higher function. The greatest among us have been preachers. ... I should like to be counted worthy to be of their company. The preacher does well to magnify his office. ... There is going to be a call before many days for a good deal of good preaching. The preacher of righteousness is put in trust with certain truths which the world greatly needs just now ; let us hope that they will be spoken with power."
From an unidentified article in Year Book and Rochester Gas & Electric News (September 1938) [combined snippets]:
We still misunderestimate youth. Even that son or daughter of yours has aspirations and capabilities which you have not yet been able fully to understand. They may express themselves in strange and sometimes perplexing ways which we often misinterpret. Youth has always been both a problem and a riddle. Even the wise men in the temple found it difficult to credit the baffling and unusual wisdom of the youthful Christ when he preached to them of old.
From a letter to the editor of the New York Herald-Telegram, reprinted in the Mineola [Texas] Monitor under the headline "War---Politics---and Time!" (September 10, 1942):
There are 10,000,000 like me in the United States. We will decide the election this fall. Don't misunderestimate us. You vote as courageously as we are willing to sacrifice and nothing in this world can stop us.
With utter sincerity, WILLARD V. MERRIHUE, Scotia, N. Y.
In more recent years—but still prior to Bush's misundercommunication—we have several additional occurrences, including some in speech (as opposed to writing).
From an unidentified story in Penthouse (1972) [combined snippets]:
Too late he realized he had severely misunderestimated her. In panic, he tried to explain the impossibility of gaining entrance, the suicidal nature of a moonlight visit on foot. There was this chap from Manchester...
From an unidentified article in Journal of the Royal Australian Historical Society (1975) [combined snippets]:
Thus Willis and Lang manoeuvered Thomas into adding weight to Game's own inclination to compromise. Thomas appears to have seriously misunderestimated both the cleverness of Willis and Lang, and the difficulties in which he was placing Game by giving him private advice and simultaneously making that advice known to the Premier through Willis.
From testimony of Charles Komanoff of Komanoff Energy Associates (July 12, 1979), in "Oversight Hearings before a Task Force of the [House of Representatives] Subcommittee on Energy and the Environment of the Committee on Interior and Insular Affairs" (1980):
I do not think, as I said, that this is politically acceptable. And I think after Three Mile Island, not only does the NRC itself understand that it sadly misunderestimated the number of ways in which nuclear accidents could take place, and how severe they could be, but also the public is simply not going to stand for a situation in which it is told that available safety measures do not have to be added to plants because they are going to cost too much.
From a capsule review of James Dawson, Superspill — The Future of Ocean Pollution in Lloyd's Shipping Manager (1980) [combined snippets]:
James Dawson analyses the hazards and looks at operating techniques. The charting of the world's oceans is woefully incomplete, he says, and hazards such as episodic waves and floating hulks are still misunderstood and misunderestimated.
From statement of Karl Hanneman, president of the Alaska Mining Association, in "Oversight Hearing Before the [House of Representatives] Subcommittee on Energy and Mineral Resources" (March 20, 1997):
With respect to the economic impacts, there are a number of things here where they have simply inadequately represented or estimated the economic impacts. One is this cost of transporting equipment to the sites. They estimated cost to plan operators ion Alaska of $470,000. Under this proposal the cost of my operation alone would be $312,000 or 66 percent of this total. I am only one of 59 operators. It is clear that they have misunderestimated the economic impacts.
Early published instances of the noun 'misunderestimation'
I also found several instances of the noun misunderestimation. From "Horses Versus Tractor," in the Port Lincoln [South Australia] Times (April 13, 1939):
A. H. Pfitnzer, Rockeby Farm, Butler Tanks, writes :—In reply to your paragraph signed by M. E. Fauser, Port Neill, I am presumably the one referred, as 'Sturdy Farmer,' Butler Tanks. 1.—I did not authorise anyone to publish anything. 2.—Yes. my horses covered (on tine correction by my men) 13,680 acres instead of 13,540 for 1938, I am sorry for this misunderestimation of 140 acres. 3.—These statements will bear out every investigation, not that it is my wish to do so. 4.—The ground is all my own farm ; I do not farm anywhere else.
From a spot item in The New Yorker, volume 47 (1971) [snippet view]:
1In Britain the Rolls story was said to be "largely one of a complete misunderestimation of development costs for the extremely advanced three-spool 211 jet.” -Chicago Tribune.
From an unidentified article in Artscribe (1979) [combined snippets]:
If the attitude of society towards the artist, for all the treacherous glamour that it casts on him or her, is one of mistrust because of this – perhaps the portmanteau word 'misunderestimation' is most appropriate – how much greater is the suspicion covering anyone who ventures further into the metaphoric without the protective insignia of 'art'.
From V.K. Verma, "High Altitude Geo-Environment and Resources: Problems and Progress," in Proceedings of the Indian Science Congress (1985) [combined snippets]:
Man and his environments are directly Affected by two basic energy systems. The first is related to the processes taking place within the earth's interior and the second is related to happenings outside the earth. A clear understanding of both systems is necessary to comprehend, control and utilize the boundless opportunities for alround progress and prosperity that the nature has placed at our disposal. There is no misunderestimation in the minds of the present-day earth scientists about the need to monitor the events that takes place in the bosom of our earth as well as in its surroundings.
And from an unidentified article in Transactions: 15th World Congress of Soil Science, Acapulco, Mexico, July 1994, volume 5, part 1 (1994) [snippet view]
Clearly, under the experimental conditions, irrigation was not responsible for pollution by nitrate leaching during the crop cycle. Conversely, it is clear that a misunderestimation of the potential mineralization of the soil, which in fact was not taken into account by farmers when choosing the N application rate, resulted in excessive N-nitrate residue in the root zone at harvest. This was responsible for important leaching during winter rains.
Conclusions
Only one of the fourteen examples noted in this example—the one from Artscribe in 1979—specifically identifies the term (in that case misunderestimation) as an intentional portmanteau word. It is certainly possible that some of the others represent unintentional typographic garbling of the intended wording. But it also seems likely that at least some of the other instances were as intentional a choice as the one in Artscribe, prompted by the writer or speaker's desire to combine the ideas of mis-estimation and underestimation. It is certainly true, as user888379 observes in a comment beneath another answer to this question, that underestimate already incorporates a notion of inaccuracy. But perhaps,as Stuart F suggest in a further comment beneath that same answer, the users of misunderestimate felt that the additional prefix added emphasis to the erroneousness implicit in the word. It may also be that the common word misunderstand exerted some influence on the word choice—although in that word the "under" component is functioning in a very different way.
Today, misunderestimate is so closely tied to George W. Bush and to the widespread critique of his use of it as constituting a verbal blunder, that any use of it now will carry that baggage with it. But it does not fall into the class of covfefe words that had no known existence before someone famous used them.