Why does Cycles sampling give diminishing returns?
Cycles and all other path tracing render engines use Monte Carlo integration. The probabilistic error after N samples of Monte Carlo integration is:



This means that to halve the noise you have to take roughly 4x more samples.

Actually, we can do a bit better. You mention skipping samples in directions that have already been sampled, and we do this to an extent. Cycles uses Quasi-Monte Carlo integration, which means it uses a sequence of random numbers that is distributed well over all directions to avoid such duplicate samples.

Quasi-Monte Carlo has better convergence than basic Monte Carlo sampling, but it's difficult to quantify and depends on the scene and settings. The integral for global illumination is high dimensional which makes things quite complicated.

To halve noise you need somewhere between 2x and 4x more samples in practice.