In a glass of water, what you observe as diffusion is almost entirely convection: temperature and salinity differences drive circulation, and the circulation mixes everything in seconds to minutes. In a brine pool the denser, saltier water sits underneath lighter seawater, so the density gradient is stable and that circulation cannot start. Convection is switched off, and you are left with genuine molecular diffusion.
Salt's molecular diffusivity in water is about 1.5e-9 m^2/s. With a diffusion length around sqrt(2Dt), that is on the order of ten meters over a thousand years, and a few tens of meters over ten thousand years. So an interface a few meters thick is effectively permanent on human timescales, and no mixing means no oxygen resupply, which is why the pool below is anoxic.
The other half is that most of these pools are not closed systems. They keep getting fed: salt dissolves from exposed evaporite beds (the Jurassic salt under the Gulf of Mexico, Miocene salt in the Red Sea) or geothermally heated brine rises and settles in seafloor depressions at spreading centers. So it is less a puddle that refuses to mix, and more a puddle being topped up faster than molecular diffusion can erase it.
Background: https://en.wikipedia.org/wiki/Brine_pool and a paper on the NEOM pools in the Gulf of Aqaba: https://www.nature.com/articles/s43247-022-00482-x
(Related rabbit hole: heat and salt diffuse at very different rates, roughly two orders of magnitude apart, which is the basis of double-diffusive convection and "salt fingers". Well studied since Turner's work in the 1960s.)