Dev news:
Decided to seperate renderable triangles from collision polygons and added the facility to define them seperatley to the map editor.
As a result, the nice rounded shape in the middle of the screenshot above is constructed of about twenty triangles in terms of rendering, but exists as a single convex polygon in terms of collision detection.
Still obviously takes longer to collide test against a polygon with lots of edges, but better than testing against than many triangles.
I tried this zone bucket thing for reducing the collision checks, but it actually ended up slower than the current method. I think that the current system is okay - AABB checking everything against everything else. I can have about 150 individual objects all bouncing against each other and the map before the frame rate slows, and only then if they are densely packed, so more than fast enough for the sorts of levels I envisage.
If it does present a performance issue later, I always have other avenues to explore to cull collision checks, but until it presents an actual problem, I'm going to leave it as it is.
The pairwise problem. Given the simplicity of the geometry that you're dealing with, and the numbers involved, I think leaving it as-is is a reasonable option. You'll probably want to do something more efficient only if you start using more polygonal collision shapes.
Someone suggested using grids and this is probably the best way to go because it is one of the simplest. The basic idea of all strategies to get around the pairwise problem is divide and conquer; If you can easily put objects into bounding regions that don't overlap, there is no need to perform a collision test. The difficulty of using this strategy is just that it involves more book-keeping work.