If it's supposed to be a puzzle for the player, then it should be based on player ability; the succubus shouldn't be able to weasel out of suspicion with just a die roll. If it's supposed to hinge on in-game character ability, then the character should also be allowed to figure out the puzzle in the first place, since the game mechanic is what is used in defense.
I think there ARE ways to solve this puzzle immediately. Some of them are listed above. A Paladin would be able to detect her as a fiend. If you suspected her and snuck into her room, you could probably find evidence pointing toward her. If you ask very pointed questions of people at the bar, you'd probably be able to guess. The PCs weren't given enough information to clue them into doing those things. They just knew someone was jealous of the succubus for stealing the man she loved. And the jealous woman was kind of obsessive so they were suspecting her.
However, I think the puzzle challenges both player and character simultaneously. The character's skills and abilities give the player options. If you are playing a Paladin, you can find out more information than if you aren't. But you aren't required to be a Paladin to sneak into her room at night or ask questions. But it's a lot simpler to say "Is that woman a fiend?"
As I say earlier in this thread, I view the character as the player's window into the game. You abilities can let you gather more or less information but then it's up to the player to use that information to solve the problem. But the player's skill at playing the game helps him get that information as well. If the player is smart, they think to use the Detect Evil ability on the right person. If they aren't, they don't.
Some groups will solve it easily. Some will need more clues. I'm perfectly ok with that. It rewards good playing and smart character creation.
Whenever I encounter plot device solution blocking as a player then its easy to just stop caring about it and go do something else. Come back to it later? Maybe if there isn't better loot somewhere else.
I guess it depends what you consider a "plot device". Everything you don't currently know is hidden behind a plot device. You don't know the currently location of Elminster but that's because your character doesn't have the ability to find that information. Not every group will be able to solve every problem. Some not at all, and some not in the same way.
True I suppose. But, by the same token, that's kind of a dick move by the player. The DM drops the scenario in front of you, it's not unreasonable for the DM to expect that you'll try to resolve the scenario. Simply picking up and leaving isn't always an option either- after all, what do you do when the other four players engage in the mystery? Sulk in the corner? It is a group game after all.
It is interesting to note that in this adventure the player in question got angry precisely because the rest of the group DID give up on the mystery. They all looked at each other and said "Well, we talked to everyone. I have no idea who might have done this. I don't think anyone else is going to give us any more information. I think we're at a dead end. We have another problem to worry about: The missing artifact that we are also supposed to find, maybe we should concentrate on that for a while and come back to this."
He got really angry because he wasn't about to give up on this problem. There had to be a solution. He was putting in the effort to solve it and had no idea why they'd just give up.
Ironically enough, he said there had to be a solution due to metagaming reasons. He said that I was running a written adventure and although it was realistic in real life to run into mysteries they couldn't solve, this was D&D. There was ALWAYS a solution to the problem and it was always accomplish-able by the players because it isn't fun to run into a problem you can't solve. So, of COURSE the authors wrote in a solution and he was going to look until he found it.
The rest of them shrugged and said "Maybe our characters aren't perceptive enough to pick up on the clues. That's what we get for playing characters who are poor at Perception and social skills".
Personally, if I'm going to tangle with a succubus, I'd prefer to find out that "Oh, that's why Jim Begoni killed himself! His girlfriend was a succubus all along, and if we'd thought to have the paladin Detect Evil on every NPC we encounter we would have picked up on it sooner" instead of "A succubus lunges at you from the open crypt. Roll for initiative." I likewise plant high-level threats for my PCs in the story long before I activate them. They still don't know about the Rakshasa in the palace...
Yes. This exactly. I'd much prefer there to be some forewarning and foreshadowing, even if our particular characters failed to pick up on the nuances. That way we can say "RIGHT! That's what those clues were trying to say. Stupid us, if we'd been a bit smarter we would have been better prepared for this encounter."
Edit: however, the one thing I would do for a threat that isn't intended to be engaged directly is prevent the players from spending too much time on it. Tell them about the murder, let them interview the girlfriend and the girl who is jealous of the girlfriend (paladin can come into play here), but after ten or twenty minutes just say, "Over the course of the afternoon, you wrack your brains to come up with a new lead or a new angle on the problem, but nothing comes to mind and you're afraid you might have to file this under Unsolved Mysteries for now. As the shadows grow dark, you're about to head home for the night when suddenly a messenger bursts into your office, shouting, 'An army of giants is approaching the city!'" in order to signal to the players (not the PCs) that the "murder scene" is closed.
As a side note, I did this. I told them that it appeared that they were at a dead end. He refused to acknowledge that and insisted on talking to more people. I let him try to get more information from a couple of people they interviewed and he failed. Then I tried to move on again and move to the next scene where someone told them about the goblin attack. But he insisted that he wasn't going to give up. Then I stepped out of character and said "Look, you're just going to hold up the game. You've got pretty much all the information you're going to get. You might want to give up on this and come back to it later."
That's what caused the argument that caused me to stop DMing. He insisted that there should be a solution readily available and I should tell him what it is now. I should name a skill and he should be able to roll it and solve the whole thing. I told him that wasn't possible as the information he was looking for wasn't really available to solve the puzzle at the moment but that maybe the information would present itself later if he just gave it a rest for now.
He got up from the table, threw some objects around and said he wasn't playing anymore.
