Sometimes I need to wish luck upon someone, and a simple "Good luck" may not suffice. For such a situation what is the correct usage? "Best Luck" or "Best of Luck"?. Why?
The idomatic and correct usage is best of luck. It really is short for I wish you the best of luck. Thus, you see why the of has to be there. The best of is a standard construction, e.g. make the best of it.
Certainly, there are situations apart from the one you describe where best luck would be correct, e.g Among my competitors, I had the best luck in finding the missing balls.
I would also like to answer this question, although @Jimi Oke already got it right, but I still feel like a lot more can be added.
The of in the best of luck means that you are wishing not the best specific luck in a specific area, but the best luck in a series of situations/decisions on a longer path in life.
So, to put this to an example, if your friend goes on vacation and you wish him the best of luck, you're wishing him the best possible outcome of all the situations he will be presented with along on his path, like choosing the best travel company, deciding properly what things to take, getting a good place to stay at, meeting good people, having a good experience on his journey with everything he comes in contact with.
But, you can wish him the best luck in only a specific thing, like, I wish you the best luck choosing the right travel company.