I don’t think the problem is actually happening quite the way you’ve described it. These Arduino shields, especially the W5100 ones, are notoriously bad at restarting correctly. If you search this forum for W5100 you’ll see quite a few threads on the issue.
To prove the point, try powering the Arduino on and off several times with the router still powered up. Eventually you’ll see the shield go into a mode where one of the LEDs is flashing rapidly and the shield won’t connect to the internet until you hit the reset button.
Some shields seem better others, and many of the cheap ones are shipped with solder bridges across the pins of the main chip, which doesn’t help.
I have eventually migrated to ESP8266 devices because of this issue, and I’m so glad that I did - they’re much nicer and more powerful to work with, and much smaller. I do have one setup with requires the use of an Arduino and an Ethernet shield and I’ve built a solution where one of the GPIO pins is connected to the Arduino Reset pin. After startup, if I can’t get an internet connection (if I can’t ping an internet server) then I pull the GPIO pin that’s connected to Reset low, causing the Arduino to reboot. It’s not pretty, but it works!