"One of the comments I got from the players earlier was that they always felt they were on a tight schedule, or had no choice but to act or else people or ideas their to them would suffer. In response I 'relaxed' the time-table of some missions. But now they just use the extra time to flee at the first sight of trouble and return super-prepared, turning a challenging encounter into a walkover. Smart, yes, fun, no."
Everyone, meet the real world. Real world, everyone.
In the real world, bad guys don't set around in thier dungeons doing nothing but waiting for heroes to show up to slaughter them. In the real world, sometimes you don't always have time to plan and debate. (I could tell a great story here about Caulerpa taxifolia, but some might interpret it as a political statement, so I'll leave it to the interested reader to google up some material.) In the real world, if you take time to advance your plans, then your opponents spend that time advancing thier own plans. Thus, there is a trade off. Every momment you spend preparing is also a momment your enemy spends preparing and growing in strength. Depending on the situation, your enemy might be using the time more productively than your are. Or, you might be using the time more productively than the enemy.
It sounds like earlier you gave the players a tight schedule which is often realistic. The player's basically knew that at all times the enemy was using its time more productively than they were, and the only way to protect thier interests was proactively disrupt the enemy plans. But inevitably, this really meant that the players were always forced to do no more than react to your fiat decisions about how the world work. Not only is this stressful, but it can leave the players feeling that they don't have alot of freedom of action. It's also not always realistic. The PC's shouldn't always arrive just at the last momment and save the world with seven seconds left on the clock. Being a considerate DM, you relaxed the time line, but now you are finding that the players are doing what skilled players always do and prepare good plans. It's worth noting that this problem is as old as D&D. In fact, alot of Gygax's modules pretty much assume that PC's will scout, withdraw, return prepared, and then wear out the bad guys in a war of attrition. If you read his early modules, and the 1st edition DMG, you'll see him giving alot of advice and guidance on how to handle this situation, and particularly on how intelligent creatures will respond to it. What you are actually experiencing is I think typical of the evolution of a group of player's. Eventually, they get smart and stop fighting the bad guys on the bad guys terms.
So, you are going to have to adapt again.
My suggestion would be set up a realistic agenda for the enemy, and give the enemy a time line. I would suggest this because few DM's can rely on fiat alone to determine what is fair for an enemy to do and accomplish. Figure out ahead of time what reinforcements the bad guys will get, what they are trying to accomplish, what advantages they will acrue over time (spells are completed, magic items acquired, defences improved, etc.), and what sort of raids and undertakings they will attempt while the PC's are away. It doesn't have to be overly detailed. You might just note that at time t+7 days (or whatever), the orcs in room #6 will get 6 new recruits, or the ogre in room #9 will gain a level of fighter, the giant plant in room #2 will add an extra HD, or the wizard in room #23 will complete a potion of invisibility, or the evil forces will raid the local temple and possibly kill the friendly cleric and make off with treasure (and probably lose some orcs from room #6 in the process). Each day that goes by, the difficulty of the encounters get incrementally worse. This won't necessarily mean that spend a day or two making a plan is a bad idea, but it will mean that unnecessary stalling will eventually put the PC's in a bad position for which they will have nothing to blame but thier own indesciveness and cowardice.
In this way, you have minimized DM fiat and with it the dangers that come from having full freedom and spontanity as a DM you won't railroad your players and probably will treat them a little more fairly. The PC's still have freedom to work up solutions. But you haven't given the PC's full freedom of action, because the bad guys are working proactively against the PC's as well.
One example of this in a published module was I6: Ravenloft. Strahd was given explicit mechanics for knowing about the player's plans, and explicit resources for intervening proactively to advance his own agenda. The longer that the PC's took to confront Strahd in his lair, the more time Strahd could spend wearing the PC party down. I wouldn't necessarily suggest giving the PC's as powerful of an advesary as Strahd, because no NPC in the history of the game was better suited to winning a war of attrition against the players than Strahd (to the point that the module was basically unwinnable when Strahd was run by a ruthless DM against a party of PC's of the suggested level), but it does give you an idea of what sort of challenges that a party can run into when they adopt a slower and more cautious approach. If the PC's try to scry the NPC's, then if the NPC's have the resources they are probably trying to scry the PC's. If the PC's plan a well prepared raid, then the NPC's will probably also plan well prepared raids on resources important to the PC's. If the PC's plan to ambush the NPC's in thier lairs, then the NPC's will probably be trying to figure out where the PC's are resting and recuperating and will try to ambush the PC's in thier strongholds.
The most dangerous NPC's of all know better than to lose the initiative by holing up in a dungeon and announcing to the world, "Here I am, come and kill me." That's like a sniper taking up position in a water tower. It doesn't matter how good the view is from the water tower, by taking up position in the water tower you elimenated most of the advantages that a sniper has.