Section 4 of this paper of Suzuki and Takahashi gives an example of a metric space -- in fact, a subspace of the Euclidean plane (so it seems you were on the right track!) -- which is incomplete but for which every contraction mapping has a fixed point.
They go on to repair matters by defining a "weakly contractive mapping" and showing that a metric space is complete iff every weakly contractive mapping has a fixed point.
Note: I was not aware of this paper until I read this question. I then googled --
contraction mapping, characterization of completeness -- and the paper showed up right away. (I look forward to reading it more carefully when I get the chance...)
"Completeness can't be omitted" is just saying that if $X$ is not complete, you can't be certain that a fixed point will exist for any given function. It doesn't mean you will never find one for specific functions.
It's like saying that "if $X$ is not complete, not all cauchy sequences converge". But you can definitely find some cauchy squences that do converge.
EDIT
It's now interesting to investigate how the theorem fails without completeness:
Firstly, here's an example of a contraction defined on a non-complete metric space with no fixed point:
$f:(0,1)\rightarrow(0,1)$ such that $f(x) = \dfrac{x}{2}$.
Clearly this is a contraction because $|f(x)-f(y)|=\Big|\dfrac{x}{2}-\dfrac{y}{2}\Big| = \dfrac{1}{2}|x-y|$ for any $x, y \in (0, 1)$. However, for any $x\in(0,1)$, $f(x)\neq x$, so there is no fixed point.
(On the natural domain of the function, the fixed point would be at $0$, but you can see that this is on the boundary of our non-complete set.)
Secondly, are there any cases where the metric space being incomplete results in more than one fixed point? The answer is no. Suppose $f:X\rightarrow X$ is a contraction and $X$ is any metric space (complete or not complete). Suppose $f$ has two fixed points at $x$ and $y$. Then $|f(x)-f(y)| = |x - y|$. This contradicts the definition of a contraction which requires $|f(a)-f(b)|<|a-b|$ for all $a,b\in X$.
Best Answer
Just take a contraction with a unique fixed point, and remove that point. For example $x \to x/2$ on $\mathbb{R} - \{0\}$ is a contraction with no fixed points.