For a reference concerning this problem, see [Cattell et al, "On computing graph minor obstruction sets", Theor. Comput. Sci. 2000][1].

I think the answer to your specific question is that it's recursively enumerable (one can test all graphs using P to see whether they belong to E) but not recursive (without further information there is no way of knowing that one has found all obstructions).

Here's a specific construction that shows this: given an instance h of the halting problem, construct an algorithm A that either recognizes all graphs if h is a non-halting instance, or that recognizes the graphs with no K_s minor if h halts in s steps. It's not hard to do this in such a way that A is always a polynomial time algorithm, but one can't tell whether E is empty or non-empty without solving the halting problem.


  [1]: http://dx.doi.org/10.1016/S0304-3975(97)00300-9