I colleague has found the Fast Hough Transform in the Gandalf library, which looks very promising but may be a lot of work to integrate, so I am looking for other approaches.

The Gandalf implementation is interesting: they evaluation the accumulator space in a recursive way as if traversing a quad- or oct-tree. Regions without much density are thrown out as they go.