Well, we know Kidd transcended from Another World to Home World specifically to save Serge, and then she must have returned to Another World. So who's to say she hasn't exisited for much longer than we thought she has? Who's to say there isn't just one Kidd with the ability to traverse dimensions at will? And who's to say that Kidd isn't a million people at once, spread across every dimension, yet due to Schala's influence and the incomplete Time Egg she carries, she IS every single Kidd, recognizing what's going on in each dimension at one time... Perhaps Kidd herself, and all her millions of dimensional selves, are controlled in unison by Schala? It's not too hard to do for the woman bound to Lavos and outside the normal flow of time-space, in the Tesseract.
Who knows? :P