I've read two books on this and my current favored solution to the Paradox is Supernovae and/or Gamma Ray Bursts. Particularly GRB as they have to ability to sterilize whole galaxies. There is a possibility even Earth has already faced one 440m years ago.

http://www.youtube.com/watch?v=7HIokbQMHB8