In the search for more efficient collision detection I decided using a quadtree was the way to go. I've think I've made good progress now. I've posted an example on my blog here.

Press Q to show the nodes when the test has started. It doesn't actually do any collision detection yet. This is just a demonstration to show how the quadtree is being built. The example isn't optimized in any way (I should be using filled rectangles instead of empty rectangles).