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).