Оба варианта верны, однако между ними есть некоторые различия в значении. 

Форма множественного числа сказуемого показывает, что в роли подлежащего выступает все сочетание, т. е. действие приписывается двум взаимосвязанным равноправным субъектам, например:После обеда Лось с Русаковым пошли посмотреть склады и магазины (Т. Семушкин); Встали и Вбропаев с Корытовым (П. Павленко).

Форма единственного числа сказуемого показывает, что подлежащим является только существительное в именительном падеже, а существительное в творительном падеже выступает в роли дополнения, обозначая лицо, сопутствующее производителю действия, например: Граф Илья Андреевич в конце января с Наташей и Соней приехал в Москву (Л. Толстой); ...Пришел Разметнов с ДемкойУшаковым (Шолохов).

Выбор одной из двух возможных форм согласования сказуемого зависит от смысловой соотнесенности действия и его производителя. Иногда на решение этого вопроса влияет лексическое значение слов, входящих в сочетание, например: Мать с ребенком пошла в амбулаторию; Старший брат с сестренкой уехал в деревню. Ср.: И графиня со своими девушками пошла за ширмами оканчивать свой туалет (Пушкин).

В других случаях играет роль лексическое значение сказуемого, например: Мать с дочерью долго не могли успокоиться и вспоминали случившееся (оба действия могут производиться при равноправном участии субъектов действия); Коля с Петей поступили в одну и ту же школу; Брат с сестрой возвратились порознь. Ср.: Клычков с Чапаевым разъехались по флангам... (Фурманов).

Иногда играет роль порядок слов в сочетании. Ср.: Муж с женой пошли в театр. – Жена с мужем пошла в театр (обычно в рассматриваемых конструкциях при различной родовой принадлежности существительных на первом месте фигурирует более сильный в грамматическом отношении мужской род, например: отец с матерью, дед с бабкой, мальчик с девочкой; поэтому выдвижение на первое место существительного в форме женского рода подчеркивает его роль, а отсюда согласование с ним сказуемого).

Слово розыскной закрепилось в русском языке в таком написании в 30-е годы XX века. Несмотря на то что написание через А предлагалось и в Толковом словаре под редакцией Д. Н. Ушакова (1939), и в первоначальном проекте академического «Орфографического словаря русского языка» под ред. С. И. Ожегова (1952, корректура), оно так и не вошло тогда в орфографические словари.

Сейчас написание разыскной вместо розыскной рекомендовано в качестве нормативного для устранения неоговоренного в своде 1956 г. исключения из правила написания приставки роз-/раз-. Написание этой приставки не подчиняется общему правилу употребления букв на месте безударных гласных: здесь в безударной позиции пишется буква А, хотя под ударением только О, напр.: раздать, но розданный; расписать, но роспись, разливать, но розлив. Поэтому и для слова разыскной не действует проверка словом розыск. Следует писать: разыскивать, разыскной, разыскник, оперативно-разыскной, следственно-разыскной, служебно-разыскной и т. п.