Dual voltage output flyback power supply - skip mode vs continuous operation
After much experimentation I find out that the cause of the problem was a degraded ESR in the capacitors on the secondary side. Solution: replace them.

How was this causing the issue I describe above? A greatly increased level of ripple on the 5V rail (the only which was regulated) was de-stabilising the regulation process, causing the supply to continuously swap between skip/continuous mode.

I do not entirely understand how but it seems that loading the 12V rail reduced the ripple on the 5V rail to the point where it made the whole supply stable.