It's actually not SQL friendly at all to store multiple values (Title and Video ID) in a single column. The data is stored as a serialized string and all you can do is to use the pattern matching operator
LIKE to get the row you're after.
For best performance you should refactor your fields and store each of them individually. If all the data has to be in one field, store the field in its own table (like Matrix fields do).
If this is no option for you, I would recommend to not use the
search parameter with your ElementCriteriaModel, but to prepare a DbCommand object using buildElementsQuery and add your "Video ID condition" using the
LIKE operator I mentioned above, so you don't rely on up-to-date search indexes.
$criteria = craft()->elements->getCriteria(ElementType::Entry);
$criteria->section = 'video';
$query = craft()->elements->buildElementsQuery($criteria);
$params = array(
':video_id' => '%video_id='.$video_id.'%',
$query->andWhere('entries.video LIKE :video_id', $params);
$result = $query->queryRow();