It took a while of testing before I noticed, then I finally realized the captcha on a web app I was working never changed!
Thankfully, before launching into some heavy-duty troubleshooting, I had a flash of inspiration: to make my unit tests work nicely I was setting the random seed to a constant (i.e. to get repeatable test data). That test data is actually being generated for every page request of the main web app (just during development).
So the fix was as trivial as calling mt_srand(time()); just before creating the Captcha (as I'm using the Securimage library, just before the $img = new Securimage(); call).
If only all troubleshooting was this quick!