I think an octree version would work quite well - should have similar/same performance characteristics for accessing neighbors and the like, with the added benefit of making longer queries faster (since you can reject things based on the highest octree level with the largest volumes).
In any case, awesome system! Thanks a ton 
I am going to use this for the dragons in my game.