I never got a 100% solution. I finally tried enough times. I think I turned it on with no Ethernet plugged in, let it boot, plugged in Ethernet and pressed the reset button. It may be the other way around, but it definitely involved having to use the reset button. Hope it helps, I may try to power cycle mine later and get a better procedure.
I had the problem you describe, an ip address which was not the one it should be, usually a different one after each reset, sometimes with parts of the address recognisable as parts of the one I was expecting.
I too tried a different W5100 module, different arduino, different connecting wires. No better.
Then I found the answer, which was to supply the W5100 with 3.3v rather than the 5v I had been using. This fixed the problem completely.
It is very odd that supplying the module with 5v stops it working properly, I can't explain it. It has an onboard AMS117 to convert the supply voltage to the 3.3v the chip needs.
Whatever the reason though, it does fix the problem. I have two W5100 modules and neither will work properly if supplied with 5v. Both work perfectly on 3.3v.
I see the instructions for the Mysensors ethernet gateway show the module supplied with 3.3v so I guess when I thought I knew better I was wrong!
@gohan I missed the * in the wiring of the PA radio and wired it to the GPIO 3.3V pin; I had assumed that since the gateway was getting the one node solidly/all the time and the other nodes not at all, there must have been an issue other than power. I must say, the power issue is mentioned often enough on MySensors.org that I should have tried that solution a long time ago.
I tried with two different Dallas Onewire and checked out the library at github. Have build these sensors before but got -127 all the time. Just adding this here if it pops up alof of people having issues...