"It's impossible because I tried but couldn't do it!" I need situations which shows that this kind of reasoning above is not working!
I do have an example, but look for more: It's so hard to cover a $6\times 10$ rectangle by pentominos (I hope no student would manage to do it), but actually possible in hundreds of ways!
Here is a nice one which I am surprised wasn't posted yet:
$\text{Prove }n^{17}+9 \text{ and } (n+1)^{17}+9 \text{ are not relatively prime for all n }$ by giving a counter example.
The first counterexample is $n=8424432925592889329288197322308900672459420460792433$.
That ought to keep your students trying for a while :)
I will reuse something I already answered another question with. I think the problem you describe will likely come up in a circumstances when we, as teachers, state and prove something is impossible (usually, an equation has no solution). It is often difficult to have students understand how such a proof is relevant, and the best way I can think of is to design a problem which is very close to the one at hand, with no obvious solution, but yet with some solution. I am not sure a general list is so useful, so I'll just pick one example.
Imagine you discussed the irrationality of $\sqrt{2}$. In other words, you discussed the impossibility to solve $p^2=2q^2$ in integers. If some students feel it obvious that there could not be a solution, then propose them the equation (also to be solved in integers) $p^2=12 q^3$. It is not obvious to find a solution when one is not familiar with the decomposition into primes, but of course $(p,q)=(18,3)$ does the job.
An old professor of mine made this point by repeated reference to aviation skeptics / skepticism. Up to a certain point in history, engineers were able to point to any number of failed attempts at machines that produced sustained flight, and no successful attempts.
A student who fails to produce example that satisfies some set of conditions and then decides that no such thing can satisfy these conditions is like an engineer who has built or observed many crashing airplanes, and decided that a flying machine cannot be built.
The question reminds of the story told about Gauss and his discovery of the constructibiliy of the 17-gon. As a young person, Gauss made the discovery and approached his professor. The professor (Kastner) dismissed Gauss because after all, the subject of straightedge and compass construction was settled since the time of the ancient Greeks. If more could be known, then over the centuries, smart people would have made the discoveries. So the construction must be impossible. What could a teenager possibly contribute?
