Maybe due to the search filter settings you have for video. Those filters to the left of the search results down the side. That's why I suggested pressing the 'All' option.
Just a thought, perhaps some results (most likely spam) were not showing due to the type not matching video types.
.