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!
Hope this helps.