Why isn't 'classic' Multi-Paxos Byzantine Consensus used for public Blockchains? Any solution to the Byzantine General's Problem can be used as a consensus method to base a distributed ledger on.

Why then, did Satoshi Nakamoto choose for the super-expensive (in electricity and CPU cycles) Proof-Of-Work?

I can think of these reasons:


Proof of Work takes time, which means that blocks take time. (But nowadays this is actually a drawback?)
Miners are paid out by the PoW. (But couldn't this work in a Multi-Paxos environment as well, where basically all miners would like to become leader for the next round?)
A Proof-of-Work chain will still work if the network netsplits into two pieces. This will create separate blocks in each half of the network, actually being a problem when the two halves are joined again (because then one of the two chains is discarded, which, if the netsplit took multiple minutes before healing, means that people and external systems might have acted based on their now-invalid balances.)


Clearly these reasons are not good enough. So what real reasons are there to use Proof-of-Work over e.g. Multi-Paxos or another 'classical' solution to the Byzantine Generals Problem?
Nakamoto Consensus has some properties that are superior to BFT algorithms. (It also has some properties that are inferior, but that's another story). 

First, BFT algorithms assume a central authority picks who the participants are. NC, on the other hand, allows anyone to attempt to win the next round.

Second, BFT algorithms generally require 2/3 + 1 (e.g. 67%) of the participants are honest. NC sets a lower threshold of 1/2 + 1 (e.g. 51%). That's because NC's PoW prevents a node from broadcasting two messages at once. 

Finally, NC has the interesting attribute that the moment a miner "wins", they also simultaneously choose the transactions they are going to include on the block. This means there is no window of opportunity for an attacker to attempt to influence the winning miner to break the rules. 

Note that Paxos is not a BFT algorithm. Paxos solves for stop-fail failures. The worst a node can do is stop working. Paxos does not solve for "byzantine" failures, where a node can try to say two different things.