There's no general rule. This analysis simply tells you if your gene set is significantly enriched in some features, so it all depends on the genes. If your genes share only general terms, you won't find anything significant, no matter how many genes you consider. On the contrary, if your genes are for example functionally related you might find some terms even if the gene number is high.

The best thing to do, in my opinion, is to select a gene set which makes sense according to some criteria, regardless of the gene number, and then try the enrichment analysis. You should never change your parameter settings just because your results are not satisfactory.

The number of genes is not as important as how the gene list was derived.  If you have thousands of genes and know with confidence that they were enriched approriately then your gene ontology analysis will be very helpful.  

All though there are 20K+ gene in genome, it does not necessary mean they have good annotation.   The usefulness of your gene ontology analysis is related to the number of genes on your list with good annotation.   If most of the genes are unknowns and can't be mapped then the ontology is not going to tell you anything meaningful.   The annotation is sometimes related to the algorithm and the annotation file you.  

Finally, the interpretation of your gene ontology also depends on your question.