Ben-Or's "Another Advantage of Free Choice" beat Rabin's "Randomized Byzantine Generals" by a couple of months in 1983. These algorithms show how much people over-extend results like FLP. The result is about a very particular system model, and the addition of even a very tiny extra piece (in Ben-Or's case, a random oracle) makes the consensus problem possible again.
I wouldn't say that these algorithms were really ignored by Lamport when he wrote the Paxos paper. Again, they're solving a different problem in a different system model. If you want to pick on Lamport, talk about Liskov's Viewstamped Replication.
If anybody has a digital copy of Ben-Or's paper that isn't partially cut off, please make it available. Both the copy in the ACM library and the only copy the author himself has are missing some of the right hand side.
A bee trapped indoors will go for the sun: a great algorithm for a forest/thicket but fatal in a house or car with windows. A fly will randmly try until it succeeds, meaning it is slower at escaping a thicket but will eventually find the open door even if it's opposite from the window.
I think a fundamental and very underrated paper and concept (which actually predates Paxos, yet Lamport ignored or was unaware of) is the notion of randomized consensus protocols. Simpler than "structured" leader type algorithms. Believe Ben Or's algorithm was first.