I've never quite understood this attitude toward divination, as any time I've experienced it a divination was more confusing than helpful. If the response is in the form of a quattrain like Nostradamus, or some other obscure and easy to misinterpret format, then the PCs still have to do just as much investigation to figure out what the divination meant as they would have done to get the answer without the divination. You can lead your players around by the nose and hand them a bushel of red herrings using divinations.
I also don't see why a world would have to be reworked to account for things like fireballs and teleportation. Unless the world is so high-magic that every farmer knows a fireball spell, it's not going to cause a major change to the way the world functions. Your average town still needs walls to keep out all the bad stuff that
doesn't know how to teleport. If you want a relatively low-magic setting, I'd recommend you be sure you make very clear to your players beforehand what you mean by "low magic", or face the possibility of having some very disappointed players down the road.