You store the key in the source code as in the other poster's description of Youtube 1.0. So employees/contractors/etc could still see the number of total videos and sequential order of uploads, but at least they can't enumerate them.

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

I would recommend a computed index (given that scheme, if you liked it; I don't, but it doesn't matter).