Just stumbled upon a very interesting paper by the author of the Voxelium blog, whose impressive research on hybrid voxel/triangle ray tracing I've blogged about in the past (see http://raytracey.blogspot.com/2012/01/voxlod-interactive-ray-tracing-of.html and http://raytracey.blogspot.com/2010/09/voxlod-interactive-ray-tracing-of.html).
This guy has invented a new algorithm for tracing incoherent rays that doesn't need an acceleration structure at all, which means no time consuming updates or rebuilds of the acceleration structure. This would also immediately solve the problem of ray tracing huge dynamic scenes. The research was inspired by a recent algorithm proposed by Keller and Wachter (toxie on ompf), which was in turn inspired by a method described in a patent of Caustic Graphics iirc.
Excerpt of the abstract:
We present a new ray traversal method based on this principle, which efﬁciently handles incoherent rays, and takes advantage of the SSE and AVX instruction sets of the CPU. Our algorithm offers notable performance improvements over similar existing solutions, and it is competitive with powerful static ray tracers
The paper can be found here: http://voxelium.wordpress.com/2012/04/24/incoherent-ray-tracing-without-acceleration-structures/