Always add stylesheets before scripts
The problem was that I’d inadvertently linked my stylesheet into the page after the Cufon script, whereas styling should come before scripts. This is covered in Cufon’s styling documentation – by linking stylesheets into the page first you’re guaranteeing they’ll load before Cufon tries to replace any text. Do it the wrong way around and your style rules won’t necessarily be available by the time Cufon tries to work its magic.
This also explains why the problem was intermittent – in some cases the stylesheet must have been cached, which side-stepped the timing problems.