To debug the problem, I installed a dedicated compass app called Compass, which displays the following:
This particular app happens to have a setting for sensor accuracy. When I set it to "Above medium", the compass suddenly works. Unfortunately many of the other apps I'd like to use the compass in don't have such a setting. I have also tried the calibration move a few times, but I don't think that's the problem, because it does work with the right settings. It's probably not related, but I have recently used my phone for Google Cardboard, which (ab)uses the magnetic sensor for user input.
What could be causing this?