The most sensible explanation has, I think been mentioned previously: that EURISKO was both overhyped and a dead end. Perhaps the techniques it used fell apart rapidly in less rigid domains than rule-based wargaming, and perhaps its successes were very heavily guided by Lenat. It's somewhat telling that Lenat, the only one who really knows how it worked, went off to do something completely different from EURISKO.
In this regard, one could consider something like EURISKO not as a successful AI, but as a successful cognitive assistant for someone working in a mostly unexplored rule-based system. Recall the results that AM, EURISKO's predecessor, got--if memory serves me, it rediscovered a lot of mathematical principles, none of them novel, but duplicating mostly from scratch results that took many years and many mathematicians to find originally.
Not that I'm certain this is the case by a long shot, but it seems the most superficially plausible explanation.
From what I remember of the papers, it was pretty clear (though perhaps not stated explicitly) that AM "happened across" many interesting factoids about math, but it was Lenat's intervention that declared them important and worth further study. I think your second paragraph implies this, but I wanted it to be explicit.
A reasonable interpretation of AM's success was that Lenat was able to recognize many important mathematical truths in AM's meanderings. Lenat never claimed any new discoveries on behalf of AM.
In the early 1980s Douglas Lenat wrote EURISKO, a program Eliezer called "[maybe] the most sophisticated self-improving AI ever built". The program reportedly had some high-profile successes in various domains, like becoming world champion at a certain wargame or designing good integrated circuits.
Despite requests Lenat never released the source code. You can download an introductory paper: "Why AM and EURISKO appear to work" [PDF]. Honestly, reading it leaves a programmer still mystified about the internal workings of the AI: for example, what does the main loop look like? Researchers supposedly answered such questions in a more detailed publication, "EURISKO: A program that learns new heuristics and domain concepts." Artificial Intelligence (21): pp. 61-98. I couldn't find that paper available for download anywhere, and being in Russia I found it quite tricky to get a paper version. Maybe you Americans will have better luck with your local library? And to the best of my knowledge no one ever succeeded in (or even seriously tried) confirming Lenat's EURISKO results.
Today in 2009 this state of affairs looks laughable. A 30-year-old pivotal breakthrough in a large and important field... that never even got reproduced. What if it was a gigantic case of Clever Hans? How do you know? You're supposed to be a scientist, little one.
So my proposal to the LessWrong community: let's reimplement EURISKO!
We have some competent programmers here, don't we? We have open source tools and languages that weren't around in 1980. We can build an open source implementation available for all to play. In my book this counts as solid progress in the AI field.
Hell, I'd do it on my own if I had the goddamn paper.
Update: RichardKennaway has put Lenat's detailed papers up online, see the comments.