Snapz...well, I guess server 4 cleared all of that up...or most of it. "Extragalactic in origin"

The flood could've evolved to be better parasites of their new hosts. That'd explain how they could change.

Think about how long it would take for the Flood to get to this galaxy from another... Even using slipspace, it would take a while. Perhaps long enough for them to change in some way? If they could survive for 100,000 years on the Halos, then they could survive just as long, if not longer, on a ship in slipspace. I bet they just stole technology from another group in another galaxy, and we probably won't get new details on that conflict seeing as how it isn't completely important to the Halo story line

The Flood's "genetic memory" includes that which allows them to create and build combat forms, carrier forms and a Gravemind(s?) form. However, this all starts out with those cute little infection forms. Those are quite portable, and can apparently survive at least 100 millenia of stasis in the Halo installations. So I suppose that wherever or whatever these beings came from they could literally catapult their infection forms in stasis in all directions, to all galaxies in view. Sure, this takes hundreds of thousands or even millions of years, but such an elementally deathlike organism like the Flood could endure all manner of punishment even in the dark confines of space.

Also of note: Marcus Lehto said something about epic landscapes from "battles that occurred 900,000 years ago) in the Halo 2 X03 video. The possibility of that depth of history is interesting now that we know just how far back a Flood-Forerunner relationship could have gone due to the Flood's extragalactic origins.