By those standards, you’d also have to hold that ‘there is a gorilla in the room’ is unfalsifiable; otherwise, what is it about the mere size of the search space that causes a claim to transition from being falsifiable to being unfalsifiable? At best, the falsification can become infeasible, but that’s not what’s relevant.
In general, a simple model of falsification is given by the argument form modus tollens: ‘If [hypothesis], then [evidence]; not [evidence], hence, [hypothesis] fails to be true’. Any thesis, about gorillas or anything else, thus is falsifiable if it leads to an implication such as is used in the antecedent above. Of course, this will in general depend on your theory, or, in the concrete example, what exactly you mean by the word ‘gorilla’. If it’s ‘a 1.8m tall, hairy primate’, then you could, for instance, assert that ‘if there are gorillas in Africa, then at any given time, at least [volume of a gorilla] of African space is occupied by hairy primate’. Given a suitable definition of ‘African space’, i.e. perhaps the volume extending from a 100m below to 100m above African soil, and you have a thesis falsifiable by an exhaustive, simultaneous search of all that space—infeasible, surely, but not in principle impossible.
In contrast, a different theory of gorillas—say, that they are 1.8m tall, hairy primates that can manipulate the minds of those observing them such that they don’t notice them—will yield a different, non-falsifiable, thesis, since you can no longer point to anything that you should observe given that there are gorillas in Africa (nothing that is different from what you should observe if there were none, at least).
Of course, in practice, you will care about practical falsifiability. One possible way to do this is soften the requirements for certainty to statistical likelihood: say, ‘if there are gorillas in Africa, then a search defined by [parameters] is 99% likely to find one’. On failing to discover gorillas using such a search, you can at least exclude the hypothesis that there are gorillas in Africa up to a certain likelihood of error; in practice, these errors can often be made so small as to leave practically no room for doubt.
People are sometimes confused by the maxim ‘absence of evidence is not evidence of absence’. This is not generally true; in fact, absence of evidence for a gorilla in my room is very strong evidence for the absence of this gorilla, quite simply because the presence of a gorilla entails me noticing it, and the fact of me not noticing it thus falsifies the hypothesis. It’s different with, for instance, the hypothesis that there’s a flea in my room: unless I carry out some specific search, I have no reason to expect finding evidence for such a flea, thus any absence of evidence for its presence does not license me to conclude its absence. However, if I were to undertake the necessary search, still failing to find the expected evidence, then once again I would be justified in concluding absence.
