Нормальное поведение.
>>> re.search(r'<.*?categ.*?>', 'kjk<div class="videoss"><a class="category_title1" href="video/#agrej">w3rtwq3t</a><a class="category_title1" href="video/#agrej">w3rtwq3t</a></div>').group()
'<div class="videoss"><a class="category_title1" href="video/#agrej">'
>>> re.search(r'<.*categ.*?>', 'kjk<div class="videoss"><a class="category_title1" href="video/#agrej">w3rtwq3t</a><a class="category_title1" href="video/#agrej">w3rtwq3t</a></div>').group()
'<div class="videoss"><a class="category_title1" href="video/#agrej">w3rtwq3t</a><a class="category_title1" href="video/#agrej">'
Имхо, ‘.*’ и ‘.+’ лучше не использовать без крайней необходимости и делать шаблон как можно более конкретизированным. Или хотя бы
re.search(r'<[^<>]*categ[^<>]*>', 'kjk<div class="videoss"><div class="videoss"><a class="category_title1" href="video/#agrej">w3rtwq3t</a></div>').group()
'<a class="category_title1" href="video/#agrej">'