Just because the Prophets do not perceive linear time doesn't mean it doesn't happen. There's no way they can meet Sisko then decide to go back and conceive him. They had to decide to conceive Sisko because "he's the one" because without Prophet Mom Sarah there would be no Sisko for them to meet later on. Even if time doesn't exist for them, it does for everyone else.
They transcend time. Just because we are slaves to time progressing at a constant pace and in a forward direction, does not mean that they have to oblige our perception of it.
What is time, really? What is life?
Look at time as if it were a film. A film is nothing but a sequence of moving pictures, at 24 frames per second. If we think of time as if it were a movie that lasts from the Big Bang to the end of the Universe, and every moment that we perceive is simply a single frame in that movie, then the Prophets are like a projectionist who can pick up that reel of film and flip through it to any point they wish. They can cut the film and splice it together in any way they want. Now imagine they can insert themselves into this movie and interact with the characters. They pick up reel #4, see this character named Sisko, and decide he's really cool. They want to influence his origin story, so they pick up reel #4 and splice in a couple scenes where they create him. They take out a pencil and draw a couple of extra scenes into a cel, and add it to the movie of the universe.
You may think this is impossible, but that's because you can't step back and see the bigger picture. You, me, the rest of mankind only exists in this film, and don't know any different. But the Prophets are like the projectionist who can see the frames of the film in any order they choose, and can even be a part of that film if they want.
That's probably why when see the Prophets, it's always via characters from the show that Sisko knows. The Prophets talk through Kira, Odo, Bashir, Dukat... they're splicing scenes from the film and adding their own language.
If they took a scene out of that film of Buck Bokai swinging at a pitch, they could splice the moment where Buck hits the ball first, then the moment where the ball is thrown from the pitcher's hand, then the moment the ball is made at the factory, then the moment where the ball is traveling across home plate, and then the moment where it sails over the outfield for a homerun. From Buck's perspective, it happened in sequence 1, 2, 3, 4, 5, and he doesn't know any different. But to anyone watching the film, it will look like Memento and be all out of order, 4, 2, 1, 3, 5.
Explaining this reminds me of the book Flatland, where the Square is frustrated at trying to explain his existence to a Point, and a Sphere is frustrated that Square doesn't understand the third dimension.
