I'm experiencing a very similar issue. I built my new PC just before Xmas and have been plagued with GPU crashes. I couldn't open a game for more than 2-3 minutes without a crash. I got my RX580 replaced last week and it hasn't really helped but I think I may be getting somewhere and it would be good if you can check this too on your system.
Once I got my new card I reinstalled windows and I was stable, games playing fine until I tried to start Layers of Fear (was already installed) for the first time, Steam then needed me to install Microsoft Visual C++ 2013 redistribute (x86 & x64), all of a sudden crashing is happening again on not only games but even web browsers. I've restored it back to before and I seem to be stable again, ran a few games that were crashing before and all seem OK. I'm running the latest beta adrenalin drivers too.
I have Microsoft Visual C++ 2012 redistribute (x86 & x64) that I installed a few days ago and this seems to not affect the system. Might be interesting if removing this solves your issue.