It's also worthwhile I think to point out that at that time, it wasn't settled that "search engines" as we know them today (like Google) were _the_ way to use the Internet. There were alternatives such as Yahoo (curated directory), and browser-side catalogs (netscape.com home page) that were much more popular. So it is possible also that AV folks weren't exactly thinking "We have to light the afterburners to go after Google in this immensely important internet search space". They might have been thinking "odd, someone spent $xxxM on hardware to run a search engine, that'll never work out".
Yahoo (aka Inktomi) search frequently took multiple pages of to find anything of quality. Curated directories were missing quite a bit. Furthermore, if I remember correctly there was some sort of payola scandal around Moz/OpenDirectory editors.
The market was primed for a better solution, and PageRank provided it.
The ability to scale in this way with commodity hardware was new and important.
PageRank was the way forward but the true schlep, in the Paul Graham sense [1], was the brute force continuous hardware scaling required to keep up with the growth of the Internet. DEC needed a technical pivot first and foremost. I've seen no evidence that the AltaVista team understood the technical challenge but I could be easily convinced that bean counters and/or management stifled a promising response; absence of evidence is not evidence of absence.
[1] http://www.paulgraham.com/schlep.html