I just want help finding a solution.
... or ask questions to better understand the situation ...
The recommended pullup strength for the NXT I2C bus(es) is 82k.
// activate internal pullups for twi. digitalWrite(SDA, 1); digitalWrite(SCL, 1);
The NXT uses bit-banged I2C that runs at 9600 bps (default).The NXT has 4k7 resistors in line on the I2C lines, so if you use 10k pullups, when the NXT pulls the line low (assuming exactly 0v on the I2C pin) it will only pull down the bus to about 1.5v (based on a 4.7v supply). If you use 82k, it will pull down to around 0.25v.
So now that it's all clear, how do you suggest I solve the problem? Is soldering a tiny PCA9517A IC the only answer? It seems there should be a rather simple solution, maybe using transistors.
I see what you mean, now I read the datasheet. Well, a simple solution would be to set up a Atmega328 as a buffer chip (cost, around $5). A couple of decoupling capacitors, and a couple of resistors and you are done. Use the internal 8 MHz oscillator. Hook up the NXT to the I2C pins with your required resistors and disable the pull-ups. Then send / receive data to your Mega using SPI (or async serial).