You really had tried it all! This is a very good overview! There are still a few things you can try.
- Try power cycling the modem (I suppose you might have done this already!)
- Try booting the system in safe mode with networking and check if the issue can be reproduced
- Check for any firmware updates for your modem
Incase you haven’t tested other devices, do that. If the DNS fails on other devices too, then it’s more likely an issue with your router or ISP.