The RX580 plot thickens: my friend managed to have the same stability issues I did and he noticed his GPU clocks were bouncing up and down before the crashes. So he applied new thermal paste and cleaned his heatsink and that made his GPU stable. I did the same and mine stabilized as well. These GPUs never reported overheating, but it seems like the issue is somehow related to thermals anyway. Maybe our GPUs report incorrect thermals or something like that?
@m_svo It was really dry when I reapplied new paste. On my friend's GPU it was even worse and most of the paste had just flaked off. In both our cases the reported thermals went down by like 5-10 degrees, so that could be the difference between overheating or not.