The thing is, the Bajorans were so ancient that they should have been able to develop warp, become techno-gods, succumb to some sort of a total collapse of civilization, start anew from stone axes, and work their way back to warp - twenty times over!
After all, according to that "Ensign Ro" quote, Bajorans had thriving cities hundreds of thousands of years ago, while humans went from those to warp in just ten thousand years. Of course, the statement in "Ensign Ro" may involve some mild exaggerating... But Picard generally isn't prone to that sort of stuff, not in matters of archaeology.
We know for a fact that Bajor had lightsails 800 years before the TV show. We don't know what else Bajor had back then, though. Today, we have hovercraft - but we also still have sailboats. Still, the controversy in "Explorers" was about the Bajoran ability to reach Cardassia those 800 years ago, with lightsail. If Bajor had at that time possessed warp or some other interstellar drive system, the controversy would not make sense. So let's argue that Bajor's best interstellar drive system 800 years prior was lightsail, and that Bajor had never had anything better even in the distant past (although the latter we cannot know for sure).
How come Bajorans didn't become techno-gods in all that time? One word: Janitza mountains.
Okay, two words. But in "House of Quark", it's stated that this mountain range has never been surveyed before our heroes set up to do it. On a human planet, this would be utterly unthinkable after millennia of civilization. Humans go places - they can't help it. The Janitza mountains prove that the Bajoran psyche is fundamentally different. Perhaps it's got something to do with their caste system. Dunno. But it's also established in "Progress" that the perfectly habitable fifth moon of Bajor was never settled by the natives until the Cardassians came - another complete impossibility if Bajorans were humans.
So Bajorans don't do things and go places. But others do. Cardassians came; no doubt hundreds of others would have done so in the preceding millennia. And once the cat is out of the bag and Bajor knows that there are space aliens, the Feds no longer have any reason not to contact them, too. If the UFP didn't make contact before the Cardassians did, then contact would happen soon thereafter, due to the waves of Bajoran refugees splashing on UFP shores...
This still gets us no closer to the question of when Bajor got warp. What we know is that they didn't have it 800 years before the show - and that they assuredly had it when the show started.
We saw a Bajoran warp-propelled vessel in the very first regular episode of the show, "Past Prologue". This vessel had been fleeing a Cardassian warp-capable ship and was saved through reaching Bajoran space: ergo, she was warp-capable herself. Indeed, many later shows would demonstrate how this two-nacelled, triangular vessel would fly in interstellar space (although admittedly always at impulse when the camera happened upon her) in Bajoran or Cardassian service. Since the vessel was Cardassian in "Rules of Engagement", we might surmise that the design was Cardassian originally, and that a few surplus vessels found their way to Bajoran hands after the occupation, probably in a state of dismal repair. The ships of this design tend to be of Cardassian yellow finish, too, perhaps further supporting this theory.
Bajor at the beginning of the show is also served by a large number of warp-capable freighters. The very first we see, in the second episode "A Man Alone", is identical in design to the ship previously used by the Bajora terrorists in "Ensign Ro". Again, this could be taken as support that the design (another triangle) is another common Bajoran warp freighter, and again possibly of Cardassian origin. In "Ensign Ro", it was a plot point that the freighter was incapable of warp, but it was also a plot point that the Cardassians did not know this - meaning that the ship was designed to do warp but had lost the ability in the hands of the Bajora, due to lack of repair.
A third warp-capable freighter is soon added to the Bajoran inventory. In "Move Along Home", the Wadi arrive from the Gamma Quadrant in a ship of distinct design. At that point, we may think it is a Wadi design, but later on it becomes a common transport in the Bajor region. A Trill delegation uses it for interstellar travel in "Rejoined"; a Bajoran scavenger has it in interstellar space in "Indiscretion". So perhaps it's a Bajoran design, and the Bajorans just gave a lift to the Wadi and the Trills? The design again offers further support for commonality, as its two warp wings are basically identical in design to the single such feature atop the "Ensign Ro" ship. A Bajoran nacelle? OTOH, again the coloration is Cardassian, and the ship has circular ridges atop and below in the very same style that the Cardassian Hideki class (first seen in "Profit and Loss") sports. Also, Cardassian allies of the Xepolite persuasion fly this ship in "The Maquis II".
So certainly Bajor is fully warp-capable for the entire duration of DS9 the TV show. It could be argued that the warp drives are non-native, all of Cardassian origin (perhaps purchased before the Cardassians turned from trade to occupation, perhaps scavenged or pilfered after the Cardassians left), but that doesn't really change anything.
What about those "impulse ships" of "Shadows and Symbols" fame, then? Most of them are freighters we have seen before - and all of those freighter designs have been proven to be warp-capable! But we can easily argue that these individual freighters were all warp-incapable, because of combat damage or wear and tear, and that this was the very reason Kira was able to use them in her blockade. All warp-capable freighters of those types would have been flying at warp on assignments already. Hell, we even spot a variant of the distinct Karemma freighter design from the Gamma Quadrant ("Starship Down") in that "impulse fleet" - probably indeed a Karemman ship stranded on the wrong side of the wormhole by the war, and doing their bit for the anti-Dominion cause.
But what about the winged, birdlike vessels forming the bulk of the "impulse fleet"? In "The Siege", Kira shows&tells that those vessels are used as interceptors, and that they possess impulse engines while Kira's small fightercraft does not. Yet both vessels were also seen in TNG "Preemptive Strike", serving the Maquis cause on attack missions that would almost assuredly have required warp drive. And the winged interceptor was also seen in the Mirror Universe ("Through the Looking Glass") where Smiley flew interstellar errands with her.
So perhaps it's once again a case of the design being warp-capable as such, but the individual ships in the impulse fleet being warp-incapable?
However, from the DS9 Tech Manual we also read that this interceptor can serve as a troop transport for 200 soldiers. This is perfectly plausible, as the hull certainly is large enough, and has a large stern door. But it's a bit funny that the same design would do both interceptor and transport duties. Perhaps the difference lies in internal layout? Perhaps troop transports are created out of the standard design by removing the warp engines? Kira's twelve impulse ships in "Shadows and Symbols" could then all have been of this variant that lacks warp engines by default, rather than damaged individuals.
To recap: we have reason to think that
1) Bajor didn't have warp as late as 800 years before the show
2) Bajor had lots of warp when the show began
3) Bajor may never have gotten around to developing native warp tech
4) Bajorans aren't explorers by nature, at least not before the occupation
5) The occupation sent lots of Bajorans to the stars, and its end sent even more
This doesn't sound too implausible or convoluted, and the only jarring thing is the "impulse fleet" in that single episode. Poor writing IMHO - perhaps influenced by the mistaken belief that earlier episodes would have "established" the impulse nature of those Bajoran winged ships.
Timo Saloniemi