Thanks!
Minor correction: I implemented hierarchical bounding boxes separately, as per Jonathan Feinberg's paper, but they turned out to be slower in all the cases I tried (even large words and areas). I was also using a quadtree to cut down the number of comparisons with previously-placed words.
In my version, once a word is placed, I copy it to the relevant position in a large sprite representing all the words placed so far. So placing a new word means it only needs to be compared with the candidate area of the large sprite, rather than multiple comparisons with all previously-placed words.
I'd like to try a hierarchical sprite version, where you compare against coarse-grained sprites first of all. This would essentially be a quadtree. The implementation would be a bit trickier because I'm also compressing blocks of 32 1-bit pixels into 32-bit integers, which also helped with performance.