You're correct. For each "column" where you wish the diminishing to occur you will need a "key" column adjacent to the original list to number the items not used yet, then a new "secondary list" made of only the numbered items, that column would only use the secondary list for its data validation.

It should be simple enough to setup the first set, then just add pairs of additional sets by copying and editing the formulas.