When failing to remember a kanji without the aid of the story, is it better to press no or yes?

I can't imagine why you would pick "yes". You failed to recall the character, so you need to learn it more, not less. Even more so without the story, since now you have even less of a connection to a memory from which to base your recollection off of.

Yes, press no. Failure is not only always an option, but the kanji you fail the most often ends up, when it finally sticks -and it will, with enough SRS time- staying in your head the longest.

The most firmly rooted memories are those associated with failure and overcoming.

Well everybody is doing this for themselves so what you should or shouldn't do can be subjective, but I also think needing to read the story calls for a fail. Unless you're using Anki and feel that you'll do with a 'hard' if you almost got it right.

Since the story contains the keywords it's a giveaway, a key to what the answer is.