Example for a non-trivial PCP verifier for an NP-complete problem
Following up on a comment by sdcvvc I checked out example 11.7 in Computational Complexity: A Modern Approach by Arora and Barak (Draft of 2008). There, the authors describe a "PCP algorithm" for the problem Graph Non-Isomorphism (GNI):


  Input: Two graphs $G_0$ and $G_1$ with $n$ vertices each.
  
  Output: Accept if and only if $G_0$ and $G_1$ are not isomorph (write
  $G_0 \not\equiv G_1$).


We denote the certificate (they call it "proof") by $\pi$ and with $\pi(i)$
the $i$-th bit of $\pi$.

The algorithm $A$ proceeds as follows:


Choose a bit $b \in \{0,1\}$ uniformly at random.
Choose a permutation $\sigma \in S_n$ (of the vertices of $G_b$).
Accept if $\pi(\langle\sigma(G_b)\rangle) = b$, reject otherwise.


Here, $\langle \_ \rangle$ is some computable bijection from $\mathbb{N}^n$
to a suitable range $[0..N] \subseteq \mathbb{N}$. We assume that if the derefenced 
bit in $\pi$ does not exist, i.e. the certificate is too short, we reject.

Claim: By above algorithm, GNI is in $\operatorname{PCP}(n \log n, 1)$, i.e.


the algorithm uses $O(n \log n)$ random bits and queries $O(1)$ bits of $\pi$,
$(G_0, G_1) \in \mathrm{GNI}$ implies that there is some certificate $\pi$
 so that $\Pr[A(G_0, G_1, \pi) \text{ accepts}] = 1$, and
$(G_0, G_1) \notin \mathrm{GNI}$ implies that 
 $\Pr[A(G_0, G_1, \pi) \text{ rejects}] \geq \tfrac{1}{2}$ for all certificates
 $\pi \in \{0,1\}^*$.


Ad 1: Clear from the algorithm by noting that uniform permutation sampling
is possible with $\approx n \log n$ random bits¹.

Ad 2: Consider the certificate

$\qquad\displaystyle \pi(\langle H \rangle) = 
  \begin{cases}
0 &amp;, H \equiv G_0, H \not\equiv G_1 \\
1 &amp;, H \equiv G_1, H \not\equiv G_0 \\
\text{arbitrary} &amp;, \text{ otherwise}
  \end{cases}$

where $H$ are all graphs with $n$ nodes. Since $G_0 \not\equiv G_1$ and
$\sigma(G_b) \equiv G_b$, we have $\sigma(G_b) \not\equiv G_{1-b}$ for all $b$ and 
$\sigma$. The query to $\pi$ therefore always yields $b$ and thus always accept.

Ad 3: Let $\pi \in \{0,1\}^*$ arbitrary and $H = \sigma(G_b)$ the chosen
query graph. If our query hits a non-existing bit of $\pi$ we reject by assumption, 
which is correct. Otherwise, we calculate

$\qquad\begin{align}
  \Pr[\text{accept}] &amp;= \Pr[b=0] \cdot \frac{\#[\pi(H) = 0 \mid H \equiv G_0]}{\#[H \equiv G_0]}
                  + \Pr[b=1] \cdot \frac{\#[\pi(H) = 1 \mid H \equiv G_1]}{\#[H \equiv G_1]} \\
                 &amp;= \frac{1}{2} \cdot \left( \frac{\#[\pi(H) = 0 \mid H \equiv G_0]}{\#[H \equiv G_0]} +
                                             \frac{\#[\pi(H) = 1 \mid H \equiv G_0]}{\#[H \equiv G_0]}
                                     \right) \\
                 &amp;= \frac{1}{2}                                         
\end{align}$
using that $H \equiv G_1 \iff H \equiv G_0$ in this case.

Thus, the claim is proven.



Some observations that helped me grasp these concepts better.


The certificate $\pi$ can be arbitrarily long and arbitrarily complex. Note that
"good" certificates for the above algorithm essentially solve the same problem
as the algorithm (many times).
But that does not imply that any decision problem can be solved in PCP style
by "just providing the answer in the certificate". Condition 3 prevents any
naive attempt of that kind.
It is in general not possible to derive an efficient (randomised one-sided-error) 
algorithm that guesses the certificate (as is the case for NP-certificate verifiers).





Strictly speaking, this assumes that $n!=2^k$ (which of course almost never holds) 
since we have infinite worst-case runtime 
for other $n$. However, Arora/Barak seem to ignore this aspect.