Do not use `flush_rewrite_rules()` on every `init`, use it in your plugin’s activation hook _once_ ([example][1]). 

Side note: `__('New Video')` is broken. Without the second parameter `textdomain` this text is not translatable. Use `__( 'New Video', 'your_plugin_textdomain' )` instead.

  [1]: https://wordpress.stackexchange.com/questions/63649/rewriting-search-permalink-with-htaccess-search-results-are-are-opened-autom/63693#63693