To avoid using an i2c multiplexer or an MCU with multiple i2c buses, you could could "roll-you-own" multiplexer using one more pcf8575.
So, 16 X pcf8575 connect to the encoders. Pcf #17 deals with the interrupts from the other 16, providing the Arduino with a single interrupt.
Pcf #18 acts as an address multiplexer for the 16 pcf. Each of its 16 outputs connects to the A2 pin of the other 16. This allows you to dynamically change the address of any of the 16, so the Arduino can then read that chip in isolation.
So on interrupt, the Arduino performs 2 read and 1 write operation, @400MHz, albeit 16 bits each. Often, the write operation would not be necessary, because the same pcf chip would be generating a series of interrupts as a decoder is turned.