Try the Search and Replace plugin: http://wordpress.org/extend/plugins/search-and-replace/
This searches for strings and will allow you to search for every instance of video-x-player, using a regex for the number. If you don’t want to use regex searching on video- will bring up every instance that is already in your database.
If you intend to keep using that video plugin you may wish to edit the plugin to give you the ID’s you want or to automatically add class names.