Perhaps i'd read the Turing award writeup to literally. "Unfortunately the setting as a Greek parable made the paper difficult for most readers to comprehend, and it took nine years from submission to publication in 1998. But the 1989 DEC technical report did get noticed. Lamport's colleague Butler Lampson evangelized the idea to the distributed computing community [19]. Shortly after the publication of Paxos, Google's Chubby system and Apache's open-source ZooKeeper offered State Machine Replication as an external, widely-deployed service."
It's a little odd, nobody seems to have actually used it before oh, say 2000 or so, but maybe it was in secret proprietary kinds of stuff.
[1] http://www.cs.yale.edu/homes/aspnes/pinewiki/Paxos.html
[2] http://amturing.acm.org/award_winners/lamport_1205376.cfm
http://apotheca.hpl.hp.com/ftp/gatekeeper/pub/dec/SRC/resear...
There were also other papers based on that before 1998, including the Petal/Frangipani stuff. That something already so well known wasn't "properly" published for nearly a decade was a bit strange, as Lamport himself explains in the page you cited.
Even if that weren't the case, something that was published in 1998 still refutes the "plagued for decades" claim.