YES!!! It is "THE SWORD OF KAHLESS"!! I ran out of subtle clues and started with more obvious ones.
Here are the explanations...
1. Someone will smile at this lunch... Kor smiles as he says the creature they just killed is lunch.
2. Good guess... Worf guesses Kor's quest, after some rather leading clues by Kor.
3. Very unlikely... Kira says Kor's story seems 'even more unlikely'.
4. An old foe returns... Toral, son of Duras, is back.
5. The second appearance of this race... A Lethean appears here, the second time we see one. I always thought this race was one of best of Michael Westmore's creations, and a shame we didn't get to see more.
6. The prototype... Kahless's bat'leth is obviously the first one.
7. Someone has a dream... Kor describes his dream in the runabout.
8. Drifting... The Sword of Kahless ends up drifting in space.
9. Unable to keep... They couldn't keep the sword because they know it will tear the empire apart.
10. Too lenient?... Kor thinks he was too lenient in his judgement of Worf after he says he declined killing Toral years ago.
11. A bit exaggerated, perhaps... Kor's story likely has some parts exaggerated.
12. A big heart... Dax says this after Kor said all three of them feasted on the heart.
13. A trio... The quest has Kor, Dax, and Worf.
14. A good dream... Kor describes the dream he had of Kang and Koloth.
15. Good thing there was no vacuum cleaner... Worf notices the dust not reaching the holographic wall.
16. A runabout is used... Obvious.
17. A lot of caves... Our trio goes through a lot of caves.
18. Unable to support the weight... The ledge Worf says is there would not have held Kor.
19. Not our destiny... Kor says it was not their destiny to keep the sword.
20. Sisko performs some maintenance... He is shaving while Dax and Worf ask for a runabout.
21. Found in the Gamma Quadrant... The world is on the Gamma side.
22. A Klingon episode... Obvious.
23. This episode takes place after season 3... A season 4 episode.
Your turn, JP.