What are the NAND Trees that Ethernet datasheets refer to?
Here is a link to a TI document that describes a NAND tree test.

Basically, the chip connects all the pins to a series of NAND gates.  Driving all of the inputs low drives the output high.  Now, you drive the inputs  individually high.  If the pin's internal connections are good, the output will go low.

This lets you test all of the pins using just one output.