Exhaustive search algorithm solving vertex cover of size $k$ in time $2^{k}n^{O(1)}$?
The search with the running time of $2^kn^{O(1)}$ is a different one. Personally, I would not have chosen to call it an exhaustive search. Not that it is incorrect, but as the question shows it may be misleading.

The classic algorithm goes as follows:


If all edges are covered, succeed.
If you already have chosen $k$ vertices, fail.
Consider the first uncovered edge.
One of its endpoints must be in the vertex cover. This leads to two possibilities, on which you recurse. In each branch of the recursion, continue at 1.


The recursion has depth $k$ and branches binarily. Thus there are $2^k$ paths in the search tree. Each step can be processed in polynomial time.

[EDIT]

Success in Step 1 means that the current candidate set is indeed a vertex cover, so the algorithm may accept.

Failure in Step 2 means that the current candidate set cannot be extended to a vertex cover of size $k$, so the search must continue in another branch.

Also, thanks to chi for pointing out an ambiguity.