Contacted AMD support, who told me to open a bug on Unofficial AMD Bugzilla. Done: 1256 – Any ETA on AMDGPU-PRO driver for R9 280x card for Ubuntu 16.04?
Meanwhile, I temporarily downgraded to Ubuntu Wily 15.10, which is the latest Ubuntu release AMD has a R9 280x driver for. No more GPU lockups with the fglrx 15.12 driver, but Ubuntu Wily is EOL as of July 28  so now I'm on an unsupported Ubuntu release, without security updates!
What are the chances AMD will release a R9 280x driver for Ubuntu 16.04?