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.
Best Answer
Seymour and Robertson have indeed said that, and in fact they wrote that in their 2003 article in which they published the graph structure theorem.
Here is the quote from Robertson and Seymour „Graph Minors. XVI. Excluding a non-planar graph“ (Journal of Combinatorial Theory, Series B, Vol. 89, Issue 1, Sept. 2003, pages 43–76, doi:10.1016/S0095-8956(03)00042-X). Their theorem 1.3 is the earliest version of what we now call the graph structure theorem.
My reading is, they were calling it a red herring because, at this point, they realized the importance of the concept of a tangle. (I think Reinhard Diestel said that the notion of a tangle is perhaps the deepest single innovation for graph theory stemming from this proof.)
Continuing the quote of Robertson and Seymour (the bold font is from me, not from the article):