I'm unfortunately still seeing this on an up-to-date Fedora 25 with kernel
4.9.6, DRM 2.48.0, LLVM 3.8.1, mesa 13.0.3, xorg-x11-drv-ati 7.7.1 (2016-09-28
git 3fc839ff) etc.

Nicolai, would it help at all to know that I don't recall ever encountering the
issue while playing non-fullscreened HTML5 youtube videos in Firefox, but that
I can easily encounter it if playing fullscreen or if playing fullscreen videos
in Totem (under GNOME Shell, whether Xorg or Wayland session)?

This really doesn't seem related to system load, I was looking at "radeontop"
just now while playing a fullscreen video (which made it deadlock within a few
minutes) and the graphics pipe was barely 20-30% used, and VRAM about 80-90%
used but never 100%.