How much of a paper does a reviewer fact-check? I'm mainly interested in the level of fact-checking of computer science conference papers. Do reviewers normally read the entire paper and exhaustively check the correctness of proofs, algorithms and claims? 

I have read papers at top conferences where implementation details are sketchy and conceptual claims are inaccurate.

My guess is that an exhaustive level of fact-checking is often not done particularly in cases where the reviewer might not be familiar with all the concepts in the paper. Is this true? If this is so, then it seems unfair that the merit of a paper is essentially just based on how well the paper is pitched in the first one or two pages.
I'm afraid there is no one-fits-all answer to your question. It highly depends on the tier of the conference. There are some that examine more into the work than others.

However, the level of scrutiny in CS conferences are generally less than that of a journal of comparable reputation. This is because, such journals go through multistage reviews and edits before the final print is published. Most conferences look only into the conceptual matter and usually have insufficient time to exhaustively implement and test the proofs of each of its candidate papers with limited reviewers.

Having said the above, there are some journals that scrutinize lesser than some conferences. Like I stated before, it all depends on the tier and reputation of the publisher.