Should you use Genetic algorithm for an extremly large unstructured search space?
No.  Just knowing the size of the search space is not enough to tell whether GA will work or not.  It also depends on the objective function (the "shape" of it), e.g., whether it is smoothly varying or not, how many local minima it has, and so on.

There is no good theory to know whether GA will work or not.  Ultimately, all you can do is try it and see.

As a side note: Generally speaking, for most problems, other approaches tend to do better than GA.  This is not a theorem; it's just experience / a rule of thumb that seems to often hold.