I do have some kind of octree in place but it's not efficient (only a 10x speedup or so for the 100k-triangle-each dragons) and extremely fragile (bad parameters will cause holes in the meshes).
Had the same problem today when I was implementing an acc. structure (AABB with uniform grids). Turns out holes in my renders are caused by
1. floating point precision issues (e.g. axis aligned planes extremely close to a boundary). Have to be relatively conservative now
2. not invalidating intersections that occur outside the current cell/voxel/... Turns out something in another cell can actually be closer than the intersection.