Player memory can be as fickle as our own.
I wholeheartedly endorse the "3 clue" or blues clues method. Sometimes you may need even more clues, or reconsider how you insert your clues.
In my campaign I utilize a tool found in most console and pc games, a "Bounty Board" that can often be found outside of public buildings. Here I can put up notices of things that someone is willing to pay to have done, be it capture or kill someone or something, fetch or deliver something, etc. If the PCs forget or miss the clues for something I want them to do, I can place a bounty for it or something that will relate to it. My players enjoy the easy out some times and when they any down time, they tend to hunt these down for their next adventure. The Bounty Board helps to bring to light NPC quests that the players may have forgotten, and can be a good introduction for rival parties also attempting to complete a bounty for the reward.
Prestige points
To help bolster Player memory, I utilize a prestige point system in my game. After each session, the players are asked to make a journal entry on our Obsidian Portal page. It can be like a diary entry of the day from the characters perspective, or a blow by blow run down from the players perspective, which they choose is up to them. They are awarded a point each session for completing them. I review them briefly to be sure no one is abusing this by just writing a couple sentences of fluff for the night. The prestige points can be used in game for rerolls and small modifiers, as well as eventually feats and ability score increases if they amass enough points. The rewards tend to be a good incentive for the players to pay attention, take notes, and do their write ups. Benefits include multiple reviews of the nights events, from different perspectives, often each including details the others missed (key for your question). The players who utilize the points, are more effective in the game, which eggs those that have not been as involved in notes and write ups to become so. The more the players do their writeups, the more they recall events, particularly after reading each others entries. At the beginning of each session I ask a player to recap the last session and describe where they were now. This helps to jog their own memories instead of only half listening to me talk at the beginning. Here is a link to our OP page with the details. http://www.obsidianportal.com/campaign/grmunky/wikis/prestige-points
"I'm at a loss for what to do here. Should I punish them ("Your words are worthless, maybe a stay in the dungeons will teach you not to make false accusations"), ignore their lapse ("I'll believe you...this time"), or what?" - So long as it does not come over heavy handed to your players, you should generally have consequences for their actions in game, or in-actions, if they fail to achieve a goal set for them. If they are stiffed a reward for not being able to prove their success, they may be more mindful of that in the future. Also stating a condition such as bringing back the head of the big bad guy, in exchange for their reward should be pointed out when they accept the quest or task.
Remember, communication is key to any role-playing game. Before getting too upset or making any large changes to the game or your style, it may behoove you to ask the players about the issues you have brought up here. Maybe they are not seeing the clues you are leaving them. Maybe they do not think they are interesting enough to persue or rewarding enough. Maybe they did not think the tasks you wanted them to do were important either to them or you, and so discounted them and moved on to what they thought was important. Maybe it is something else entirely. Addressing the issue, letting them know that it is an issue for you, will hopefully bring to light the best answer for you and your group. No matter what, the goal is mutual fun, good communication, and respect.