Arduino Mega 2560 and W5100 (non-shield)

Using Arduino Networking, Protocols, and Devices
3

Mat, it really seems you have tried hard to figure out the problem and explained it well.

Some thoughts to check with you:
Do you have in your setup() code something like the following;

pinMode(10, OUTPUT);        // set ethernet CS as output:
pinMode(53, OUTPUT);        // set ATMega-2560, pin 53 hardware cs pin output, even if un-used:

Also, have you tried with a small delay, say like delay(250) in the setup() to allow time for the ethernet CPU to reset before using it?

Paul