Electronic – Multiplexers/Demultiplexers

First, presumably you've already looked at assigning channels by geometric convenience rather than number and decided that doesn't solve your problem.

A CPLD could give you a lot of pinout flexiblity, but perhaps would be "cheating" by your goals (though there were board-level mainframe CPUs that used early PALs).

On the novel front, if your delay budget is generous an (E)PROM loaded with a suitable truth table to use address lines as channel and select inputs could be a solution. Perhaps you are already using something similar to hold a table for instruction decode or even microcode.

A more off-the-shelf solution might be to use tri-state buffers on each side, with only one enabled at a time, or even at an extreme, open-collector logic gates and a pullup.

An easy approach would be to use hardware SPI to read shift registers serially.

You could daisy-chain as many 8-bit shift registers as required. If you use 74HC165 you could simultaneously sample each switch (1/8 74HC165, 1 resistor required per switch) and then shift the data to the micro at perhaps 10MHz, so you could get 1000 switch states in 100 usec or 10,000 in 1ms. 10,000 inputs would require 1250 shift registers so you would need to buffer the clocks and/or reduce the shift rate.

Physical bus length will become a problem at high clock rates- you have to make sure that datasheet setup and hold times are observed.