What I did
I set up the firewall installed in Mac OS X to limit the bandwidth of the connection to the AirPort, so that print jobs go more slowly to the printer. This is easy to do, once you know how (detailed below).
Why I did it
Looking at the traffic between Mac OS X and the printer using Eavesdrop (nice tool, thank you), I noticed at the same point in the conversation that the printer would stop. Let me be clearer: it was always at a particular point in the protocol, not the same point in the job. I guessed, and it was a guess (don't know if it's correct), that traffic was heading over to the printer too quickly and it just couldn't cope.
Read the rest for the details on how I limited the connection speed to the printer...
How I did it:
Looking through some manual pages if ipfw and dummynet, I saw you could limit bandwidth on a network connection with very fine granularity. The possible fix is, then, to limit the connection to the printer over the AirPort Express (and I guess Extreme) to a very low bandwidth. From Terminal, I typed in the following:
sudo ipfw add pipe 1 ip from any to 192.168.1.3 10000
and then
sudo ipfw pipe 1 config bw 1Mbit/s queue 10
Now, these were adapted from the man pages and I'm no expert, and so I can't be sure they're the correct or best settings. Here's what I think they do. The first command states that any traffic to 192.168.1.3 on port 10000 (that's my AirPort Express device, remote usb printing port) should be put in a pipe for processing. The second command states that the pipe should have a maximum bandwidth of 1Mbit/s, which is relatively slow for my network (usually runs at max 54Mbit/s). (Honestly, I don't know what the queue 10 does.)
Now jobs go to the printer happily. It's a bit slow, and sometimes slows to a line at a time, but I can live with that, and I will experiment with higher bandwidths.
Of course, this may not work for you. It may hurt your machine in ways I don't want to be, and won't be responsible for. It may not work with your printer: I don't have others I can test. But I can print again. If you want to experiment, feel free to comment with your results and settings.

