In the final act, how to drop clues without causing players to feel "cheated" they didn't find them sooner?

Question

I'm a bit of an "on the fly" GM: in terms of writing a story, I prefer to sketch out the skeleton, and add flesh as the players move along the limbs. The quest to find the Plot Device, at the skeleton level, is intended to crown the adventure. Having arrived at the final stages of enfleshment, I am noticing some connecting ligaments on this body are perhaps not where they should be.

In the adventure I am running, the players have known about the missing Plot Device for some time, but haven't looked into it much. I haven't dropped many clues about it, and I think they've picked up on the general late-gameness of the quest for the Device - and there's been a lot of other plot threads to deal with in the meantime. However, out-of-session a PC has just breached the subject of the quest, and this will obviously result in a renewed focus on the objective. I'm realizing that I would have preferred the group to have a bit more information about it this late in the adventure.

So far, they have received three main clues. Another source of info could be the three NPCs that know its location.

1. It's common knowledge that the Plot Device was lost in a wide wasteland.
2. The players have also (unknowingly) seen an image of the location of the Device, although the image has since been incidentally captured with a trove of other archives as part of a larger raid by a traitor PC-turned-NPC, who similarly does not yet understand its significance. The image depicts an exponentially powerful energy source (note: the energy source is not the Device).
3. The players have picked up something like an aircraft's black box from a failed expedition to find the Device.
4. The BBEG, his partner, and his henchman all know where it is, but they really want to keep it there, and don't need to use it or visit it, so long as it stays put (which could conceivably be a concern, granted).

The fact that the Plot Device has been missing for years is a vital aspect of the world, so it is difficult to justify handing out clues to players who simply decide to do a bit of research or asking around. What's worse, the in-game expeditions have failed to find the Device for years, so this thing needs to be extremely hidden in order to preserve suspension of disbelief. But with no idea of where to start aside from an extremely large area of inhospitable territory, I fear that they'll assume it's just lost for good, and lose out on what I intended to be the bookend on a so-far thrilling adventure.

So: next session is coming up. Generally speaking, what kind of new clues could they find, that would not end up violating the premise that the Plot Device is Hide and Seek Champion of the World?

Answer 1

Hide the clues in an inaccessible location

High level adventurers go to places nobody else goes to live and tell the tale all the time: fallen cities in the frozen waste, ancient crypts full of undead, storm encircled cloud castles, pocket dimension mansions of forgotten liches in the astral plane. Hide the clue to the location of your Plot Device, whatever it may be, there. It is absolutely rational and believable that nobody else has yet found it, because nobody has been to those places (and returned) in ages.

In addition, there must be a way to learn about where the Plot Device is, otherwise the antagonist, his partner and henchman would not be able to know about it either. If the PCs are already on the tracks of these NPCs, they may find clues hidden in any of their lairs or locations. Even if these NPCs have no interest for the Device to be found, they may still have libraries, laboratories or diaries with notes and plans.

My last point is: do not only hide one clue. DMs notoriously overestimate how easy it is for players to pick up on clues. Players do and can not know what of the many leads they encounter is about a central device of the story, and what is about an irrelevant side quest. Follow the three clue rule, and at least provide three different sources for this information -- both how important the Plot Device is, and where to find it.

Answer 2

Make a backstory for the device that leads to a surplus of hints

The easiest way to sprinkle clues around is to have a lot of them that can lead in a bunch of directions. So, have a backstory with several elements.

1. Prototypes which they can find with partial functionality which hint at the nature of the device and where it might hide.

2. Rare resources and supplies which were needed to make it, looted from a variety of locations.

3. Crafters who were recruited to build parts for it.

4. Fights between people who sought to steal or disrupt the device and the creators.

5. Legendary creatures slain to help create the device and the chaos their departure has left.

This means there can be a lot of clues to hype up the device which will give small hints as to the location- perhaps it requires a rare resource, or someone knows hints about where it was, or perhaps it emits an energy which someone can detect. You can drop minor hints as to its location and there can be decoy prototypes which people can discover and gain great wealth.

Have enemy action stop attempts.

The BBEG presumably doesn't want it found. As such, for the real device, make it so someone did find it. One of the many expeditions did gather the right clues (but not as well as the PCs who have a larger selection of clues) and attempted to find it, but interference from the BBEG and local horrors led to their horrible deaths. When the PCs finally track it down, they can find more black boxes, corpses, and hints that this is the real one.

Answer 3

Someone just tells them

It can be a little subtler than that, but what if someone else out there has already found an important clue? And has learned that the heroes are capable of retrieving the Plot Device?

• Enemy of their enemy. Someone opposed to the BBEG also wants the Plot Device -- either to use it themselves, or to keep it out of the Evil One's hands. He knows something, such as which region of the Vast Wasteland is the right place to look. And this person has heard rumors about the party, and hires them.
• Look who's back. The traitor, because he's now an NPC, has somehow discovered the significance of that image. He realizes that his old friends have more information, even if they don't know it, so he shows up to make a deal.
• The Witness. The next time the party ransacks one of the BBEG's lairs, they meet someone who knows something - a prisoner, a ghost, a long-lived creature who lives in the walls, or someone else who had overheard the BBEG discussing a very important point. Surely they're willing to give up the information for a price. Or maybe the lair contains a scroll of Speak with Dead or Stone Tell that lets them party ask questions of the bodies or the walls (although it sounds like the PCs may not think to use that!)