I've committed changes to the netbsd/mips config for EGCS which work
around the remaining problems.  There are a bunch of minor changes to
config/mips/netbsd.h, and one major change: I've turned on the
'-mdebuga' flag by default. That flag stops GO_IF_LEGITIMATE_ADDRESS
from pretending that the mips CPU can handle an address mode of 32-bit
constant plus a register.  

For the addresses that the mips can handle (16-bit signed constant)
plus a register), breaking up addresses and doing CSE will result in
strictly worse code than just backing out the changes to expr.c which
caused the problem; but that would hurt other ports.

Caveat: there seems to be no way to turn of -mdebuga.