> Nearly all spreadsheets are "small", and most of those users don't
> want to pay the costs for "unlimited" capacity.
If they have a fixed-size array in there somewhere, then those users with "small" spreadsheets are now paying for ~1000 columns that they're not using. If they're using anything more complex than a fixed-size array - and I imagine that they are - then they're already paying those costs. So I don't think this is a space/time/complexity thing.
My guess is that they are trying to save some bits somewhere by packing row and column number, plus some other bits, into a word. (I have a vague recollection that Excell has a 64k row limit because it uses a 16-bit row number somewhere.)