Maybe you could split the ID into two parts: the first is an encrypted integer representing the DB row, the second is a "password" for the video. Then you get fast indexing but you still can't enumerate videos without the ID.
You could also maybe rotate the key once in a while, but only for videos created after the rotation, and indicate the "key version" with a third field in the video ID