I've done the ad lib in the past, but ever since I watched Babylon 5, I've been unable to think of D&D in anything less than an epic storyline that involves detailed planning, especially if you want to preserve options for the PCs instead of steamrolling them into a single path.
Every once in a while, though, when the PCs are particularly frustrated with a long term puzzle or when they can't figure out where to go, I'll throw some semi-ad lib aspects into the game to keep them from being too frustrated.
For instance, the party had been attacked by a wizard who managed to get away with their bag of holding. They spent the next five hours arguing about how to hunt down the wizard. The frustration levels were so high that they were disregarding the subtle hints I kept dropping to get them on the right track. Realizing that the session would soon end on a major down note, I flipped through my files and found an old enemy of the PCs, the only assistant of a BBEG that escaped from a prior adventure, and let them spot him walking down the street outside the window of their tavern. They sprung into action against him and his two bodyguards (who were fighters straight out of the DMG NPC section) and had a very interesting battle in the middle of the street. When he finally fell to the PCs, their frowns had become smiles and they felt great. Right after they finished dividing up the loot from the battle (and dealing with the city guard), the change of pace paid off: they figured out the clue that they had been missing and prepared to go after the wizard that stole their stuff during the next session.
