While it is true that every configuration of a Rubik's cube can be solved in 20 moves or less, relatively few of them actually require that many. The number of configs that require 20 moves is as yet unknown, the estimate is 490 million as can be seen in the third table shown here. While that may seem like a lot, as a fraction of the 43 quintillion total it is quite small:

490,000,000 / 43,252,003,274,489,856,000 = 0.0000000001 
                                            (rounded)

Hence the odds that any given random cube actually requires 20 moves to solve are slim to none. For a better idea of what to expect for an optimal solution see the bar charts here which show that a 17-18 move solution is the most likely.

While it is possible to get a solution in the optimal range with a two-phase solver relatively quickly, proving that it is actually optimal can be much more time consuming. For example, consider an 18 move solution with search depths of 10+8 which means that the solution was found at depth 10 in phase 1. To prove that the solution is optimal requires completing the search through depth 17 to show that no shorter solution exists. Each higher depth takes 13.35 times longer to search than the previous so the expected time to go from depth 10 to 17 is 13.35^7 = 75,573,382 times longer than the amount of time required to search depth 10 (note: the 13.35 growth rate can be seen here).