This is a follow-up question of media9.sty not found.
Basically, I had to synchronize MikTeX in order to get the package.
So, how often do I have to synchronize MikTeX in order for it not to miss any package?
It depends on the activity of the package writing community. Whenever a new package arrives on CTAN (half a dozen per week, I guess) it takes a few days until they are available in MiKTeX. If you don't want to miss any of these, do one database and one package update per week. New packages are announced in the comp.text.tex newsgroup.