I'm using cube mapping with the depth packed into RGBA as described by Phantom here. Before this I had tried virtual shadow depth cube maps, apparantly described somewhere in ShaderX 3, although I don't have the book, but failed due to indirect cubemap sampling causing an error for some reason. I'm planning to try variance shadow mapping with 2 component floating-point cube maps once I finish this implementation.
Obviously there are problems here. First thing I'm going to do is render backfaces and try glPolygonOffset for bias. Once the noise is gone, I'll try some manual bilinear filtering, or maybe some cubic filtering (described in GPU Gems 2 I think).