Jedediah Berry's Manual of Detection is the most surreal mystery I've ever read, except maybe for Auster's New York Trilogy. In fact, it's hard to see why the publisher packaged it as a mystery at all, and not as general literature (like, again, the New York Trilogy). In the end, though, I just read books, I don't choose the genres, and this book was a really wonderful one.
Unwin, the protagonist, starts as a clerk in a huge detective agencies, assigned to a detective who's solved celebrated mysteries like "The Man who Stole Tuesday." He's promoted to detective, and in the course of the novel ends up in the middle of a case where all of the city's alarm clocks are being stolen, entering dreams through vinyl LPs, and discovering the identity of "The Last Victim." I think that these kinds of stories stand or fall on how well they hang together. They don't necessarily have to make logical sense, but they can't be totally random either. For this kind of story to work, you have to feel at the end that there's an internal logic that's held up, and Berry pulls it off.
More famously surreal, of course, is Kafka's Metamorphosis, which I finally got around to reading this weekend. I don't know that I have anything to add to the mounds of analysis that have been written about this story, except that I think that one must have at least a somewhat literal reading. I think the story loses a lot if you read it as completely symbolic. I also think a symbolic reading is much too reductive.
Redbreast, by Jo Nesbo, is straightforward by comparison. It was a bit odd to read the blurbs in the front-matter, and go in expecting a whole take on neo-nazis in Norway, and end up with a Day of the Jackal-type novel. In a way that's good, though -- as a non-Norwegian, I'm not sure how much relevance a treatise on intolerance in Norway would have meant to me. But I am sure how brilliantly Nesbo ratchets up the tension through the novel, and what a great character Harry Hole the lead detective is.