I know that a character who solves a murder mystery by just asking the victim what happened is still engaged in investigation, so its not like the story didn't happen. But the ability to bypass interviewing witnesses and scrounging for clues by the use of magic circumscribed my ability to tell an investigative story more than it helped.
As an aside, have you ever seen
Pushing Daisies? It's an investigative TV show where the main character basically has the power to
Speak With Dead (with a few caveats). He usually speaks with the corpse within the first fifteen minutes of the show, and then spends the next 45 minutes trying to make sense of what the corpse said.
So, yeah, you can use magic to enhance a storyline, not to provide an instant "I win".
In fact, that's what I had in mind with my earlier mentioned "CSI: Eberron" model. Since players KNOW going in that it's an investigative game, as opposed to a combat game, you'll see players make characters with that in mind. I'd be making a streetsmart Spellthief with ranks in Bluff, Diplomacy, Gather Information, and Streetwise - and if we used the Contact rules in UA, a bunch of street-level contacts. You might make a bard, or a diviner-type wizard, or a sorcerer focused on Speak With Dead.
Our adventure will probably have those talents in mind. We could speak with the corpse, and get a vague clue as to who the killer is. Or, we might not even be able to find the corpse, because it's been animated as a zombie and is now killing people. When you use Detect Evil to find the bad guy in the slums, you suddenly realize that you're standing in a PIT of evil, and it's hard to find the villain. And so on.
Compare that to 4e, as written. We know we're in an investigative game. So, we start taking classes. Now, I could be a rogue or a bard, with some very useful skills (Bluff, Diplomacy, Streetwise, Thievery, Perception)... or I could be a wizard, with some useful rituals. Now, let's say I go with the rogue... since most of the feats are based around combat (Which isn't going to be as useful in this game), I might take Ritual Casting - meaning, I can now do most of the same non-combat things as our mage. Our mage, trying to stay even with the rogue, takes "Jack of All Trades" (+2 to all untrained skills) as a feat... or starts taking training in useful skills.
The overlap between characters in 4e, as written, is rather large. To be honest,
I like this, but only in a combat-based game - it gives characters a range of backgrounds. But, in an investigative game, this level of play is not as well supported as it was in 3e.
I really should clarify something I said earlier, though. Earlier, I said something along the lines of "4e Doesn't do Investigative as well as as 3e did". What I mean is, as-written, 4e doesn't encourage investigative play as well as 3e. You could argue that many 3e powers nerf investigative play (Speak with dead, for example, though I've given examples in this post how that spell can be used to ENHANCE the scenario) - but the fact is, they're there. They are in the game.
As for Cthulu in D&D, I have run it in both 2e and 3e. When I ran it in 2e, I wasn't familiar with Lovecraft, but the horror adventure I ran wound up being very Cthuluesque. When I ran it in 3e, I used the sanity rules from CoCd20, and the game was a blast. Both worked fairly well, because the culture of the game had been modified to discourage direct combat. I think, in 4e, it might be a bit harder to modify the inherent assumptions of the game to support a "run away!" style of play. When characters are 95% hammer (ie, Combat), everything starts to look like a nail.
Hopefully, we'll see a 4e Unearthed Arcana which we can use to tweak the game to our heart's content.
There's a lot of debate over whether or not 4e can run investigation or cthulu horror. But what other genres does it have a problem running? And, to broaden the question a bit, beyond basic combat, what sort of genres is 4e GREAT at running? I believe I mentioned that it runs large-scale combats (20+ participants) pretty well. I could imagine using it to run a Vietnam-like campaign, against jungle-dwelling orcs. I think, as a whole, 4e fits pretty well with Eberron (though some tweaks need to be made). I imagine it could also be used to run a DARK SUN game better than 3e ever did (because the game burns out much of the inherent magic in the classes that happened with 3e).