Rule-wise, a duration effect is not dependant on whether the card has stayed out in play. Having it stay out is just for player comfort. So while premature clean-up breaks the rules, it won't actually cost you the duration effect.
If you get the effect, you should also have the card stay in play. Why? Because of something we here call "missing the reshuffle". If you shuffle your discard pile before discarding a duration card, it will not be in your next deck. If you place the discard before, it will. Therefore, sometimes a player might get an advantage of breaking the rules if you don't make him undo his mistake.
My advice: Allow and demand fishing it out. If you want to avoid players using that as a chance to look through their discard intentionally, make another player (chosen by the premature up-cleaner) fish it out. Losing the duration ability might work as a house-rule punishment for the discard, but as pointed out, there might be occasions where even this can be abused.
Allowing to get the card is not ideal, but probably the best you can do.