The Robertson-Seymour theorem on graph minors leads to some interesting conundrums.
The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As testing for the presence of any given minor can be done in cubic time (albeit with astronomical constants) this implies that there exists a polynomial time algorithm for testing membership in any minor-closed class of graphs. Hence it seems reasonable that problem should be deemed to be in P.
However the RS theory does not give us even the faintest clue as to how to determine the guaranteed-finite set of excluded minors, and until we have these at hand, we may not have any algorithm of any sort. Worse still, there is no known algorithm to actually find the excluded minors and even if you have a big list of them, there is no way that I know to verify that the list is actually complete. In fact, could it perhaps actually be undecidable to find the list of excluded minors?
So, does it make sense to view a problem as being simultaneously polynomial-time and undecidable? It seems a bit odd to me (who is not a particular expert in complexity) but maybe it's quite routine?
Best Answer
Consider the following simplified example of the same phenomenon, which many students find clarifying.
Let $f(n)=1$, if there are $n$ consecutive $7$s in the decimal expansion of $\pi$, and otherwise $f(n)=0$. Is this function computable?
A naive attempt to compute $f(n)$ would simply proceed to search $\pi$ for $n$ consecutive $7$s. If found, the algorithm outputs $1$, but otherwise....and then the naive algorithm doesn't seem to know when to output $0$, and so students sometimes expect that $f$ is not computable.
But actually, $f$ is a computable function. If it happens that there are arbitrarily long sequences of $7$s in the decimal expansion of $\pi$, an open question, then $f$ is the constant $1$ function, which is certainly computable. Otherwise, there is some longest sequence of $7$s in $\pi$, having length $N$, and so $f$ is the function that is $1$ up to $N$ and then $0$ above $N$. And this function also is computable, for any particular $N$.
So the situation is that we have proved that $f$ is computable by exhibiting several algorithms, and proving that $f$ is definitely computed by one of them, but we don't know which one. (In fact, $f$ is linear time computable.) So we have proved that $f$ is a computable function, but by a pure existence proof that merely shows there is an algorithm computing $f$, without explicitly exhibiting it.
It seems to be the same phenomenon in your case, where you have a computable function, but you don't know which algorithm computes it.
Addition. Let me try to address Thierry Zell's concern about the third question. To my way of thinking, the phenomenon of the question is an instance of the problem of uniformity of algorithms, a pervasively considered issue in computability theory.
To illustrate, consider the question of whether a given program $p$ halts on input $0$ before another program $q$. Let $f_p(q)=1$ if it does and otherwise $f_p(q)=0$. Every such function $f_p$ is computable, for similar reasons to my $\pi$ function $f$ above, since either $p$ doesn't halt at all on input $0$, in which case $f_p$ is identically $0$, or $p$ does halt in $N$ steps, in which case we need only run $q$ for $N$ steps to see if it halts, and give our output for $f_p(q)$ by that time. So each $f_p$ is a computable function. But the joint function $f(p,q)=f_p(q)$, a binary function, is not computable (if it were, then we could solve the halting problem: to decide if $p$ halts on input $0$, design a program $q$ that would take one step extra after a halt, and ask if $p$ halts before $q$).
In other words, the function $f(p,q)$ is computable for any fixed $p$, but not uniformly in $p$. And such uniformity issues are ubiquitous in computability theory.
In the example of the question, each class of graphs is decidable, but not uniformly so, since by Tony's answer there is no uniform algorithm, given a description of the class, to find the collection of excluded minors. But for any such fixed class, the membership question is decidable.
The issue of whether a given algorithm is uniform in a given parameter is a very common concern in computability theory, and occurs throughout the subject.