IMO there's no perfect recipe, as the best adventures are a mix of elements and the exact proportions must be tailored to the taste of your gaming group.
For me, an adventure does not tell a story. "Story" occurs when the players interact with the elements of the adventure. A good adventure for me is a bit more sand-boxy in that there are several potential story threads woven into the adventure, any or all of which the players can choose to follow. A good adventure, played by different gaming groups, will tell different stories depending upon the decisions the group makes.
A perfect adventure allows several ways to accomplish tasks and overcome obstacles. If there is a primary story thread in the adventure, there are multiple ways to reach the objective. Perfect adventures are non linear, and often provide two or more differing choices; even when that choice is only whether the party takes the left or right corridor, going left versus right results in a different adventure path. Some obstacles might be more easily overcome by some means than others, but relatively few encounters should be designed to be overcome by one method solely (roleplaying, combat, puzzle). Some may even combine several methods.
A perfect adventure provides more than just the base adventure site; it combines some exploration (potentially a mix of civilized, wilderness, and dungeon) with encounters (people, monsters, or elements of the environment to be interacted with). There should be some of the history left untold, some sense of wonder and a perception that there is much more going on "behind the scenes". Lore should be deeper than what can be seen at first glance. Ideally, there are some encounters that are "off the beaten path" that can be explored because they are there in the world and not because they are integral to a specific plot.
The perfect adventure has memorable characters with whom the PCs can interact, potentially on multiple levels and with repeat engagements.
The perfect adventure also ends with more hooks that can lead to other adventures and sequels - -the only adventures which wrap all of their loose ends up in a bow are the ones that end campaigns.
For old schoolers,
T1: The Village of Hommlet/T1-4: Temple of Elemental Evil,
B2: The Keep on the Borderlands, and
B4: The Lost City are examples of adventures that contain many of the elements of my "perfect" adventure.
The Lost City of Barakus is great example from the 3E era that contains most of these elements; other adventures contain individual pieces but not all.
I've found few 4E adventures that fit the bill, as most seem to be focused on individual encounter design that sacrifices adventure structure resulting in an overly-linear adventure. In
Raiders of Oakhurst: Reloaded, I tried to write a short 4E adventure that contains many of my philosophies on adventure design. I think it demonstrates most points given the relatively short nature of the adventure -- you'll have to let me know if I've succeeded.
(Edit:
The Grumpy Celt has a comparison of a D&D Classic,
U1: Sinister Secret of Saltmarsh with
Raiders of Oakhurst: Reloaded which provides some humorous discussion of adventure design.)