Well control weather only has a radius of a couple of miles. In a 250,000 square mile area it's still going to be pretty much a needle in a haystack. (What the heck, why in the world is this a lower level spell for wizards than druids

)
Well depending on how much information they have, scry + teleport might put them close. Of course you said the tower was shielded against divination so it depends on how strong this shielding is. However if they know of an individual they could catch outside the tower that does know it's location then that might work. But I wouldn't have high hopes for this, again the chance of doing the right thing at the right time seems really slim.
A legend lore might provide some useful info, since that doesn't really target the tower. Though I doubt it would yeild anything useful enough to get them where they want to be in any decent amount of time.
They could always research a spell specificly for this task, since it looks like finding it any other way would be incredibly time consuming anyway.
Another thought, if there is a cleric that can cast commune, you might be able to greatly narrow down the search area. Take a map of the area, doesn't have to be detailed, or exact, just basically correct. Draw a line down the center, point to one side, "is the tower we seek in this area?" If the answer is no draw a line dividing the other half in half again the other way (if yes, the same half) and ask again. then divide that sector down and ask again. If I haven't completely screwed up my math this would narrow the search area down to approximately 32 sq miles. In an area that small, a few control weather spells would do the trick. And of course a second casting of commune would pretty much put you on top of it, though I wouldn't bug my diety twice in one day, but thats just me.