For a reference concerning this problem, see Cattell et al, "On computing graph minor obstruction sets", Theor. Comput. Sci. 2000.
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.