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.