При написании сложных прилагательных имеет значение не только тип связи между основами (сочинение / подчинение), но и наличие или отсутствие суффикса прилагательного или причастия в первой части слова. 

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

В прилагательном минно-разыскной подчинительное отношение основ, но наличие в первой части суффикса приводит к появлению дефиса. Руководствуемся словарной фиксацией.

Правильно: минно-разыскная собака. Прилагательное минно-разыскной зафиксировано в академическом орфографическом словаре, размещенном на ресурсе «Академос» Института русского языка им. В. В. Виноградова РАН.

Написание подчиняется правилу о приставках и зависит от ударения: http://gramota.ru/spravka/rules/?rub=gl&text=19_7

Современной орфографической норме отвечает написание разыскной, хотя раньше верным признавалось написание через О (розыскной было весьма странным исключением из правил, о котором в самих правилах не говорилось, поэтому в орфографических словарях последних лет это исключение устранено). Об истории этого слова см. также в ответе на вопрос № 187553.

В принципе такая фраза возможна.

Хороший вопрос, и он стоит того, чтобы поразмышлять о судьбах русского правописания. Ведь гораздо чаще в вопросах наших посетителей можно встретить противоположную точку зрения: зачем вообще нужны изменения в орфографии? Неужели лингвистам больше нечем заняться?

Революции в правописании точно не случится. Во-первых, любые попытки внести изменения в свод орфографических и пунктуационных правил – изменения даже самые незначительные и необходимые – вызывают крайне болезненную реакцию со стороны общества (вернее, его большей части – грамотных носителей языка). Это понятно и объяснимо: усвоив правила правописания, люди не хотят переучиваться. Устойчивость орфографии – необходимое условие существования культуры, а грамотность – важнейший показатель образованности человека. При реформах правописания страдают именно самые грамотные люди, т. к. они вмиг (пусть и на короткое время, пока не усвоят новые правила) становятся самыми неграмотными (Если, например, мы примем предложение писать парашут, брошура, жури, то грамотный человек, выучивший, что надо писать Ю, сделает ошибку, а неграмотный, никогда не слышавший ни о каких исключениях, напишет правильно). Именно поэтому любые предложения об изменении орфографии моментально встречаются обществом в штыки: лингвистам «достается по полной», а их аргументы часто остаются неуслышанными (так произошло и несколько лет назад, когда обсуждался проект нового свода правил правописания). Кроме того, очень многие (под влиянием уроков русского языка в школе, где, в основном, изучается правописание) ошибочно думают, что правописание и язык – одно и то же, что изменения в орфографии ведут к изменениям в языке. Хотя на самом деле орфография – лишь «оболочка» языка (как фантик конфеты), и, изменив ее, мы навредить языку не можем.

Во-вторых (хотя это, наверное, во-первых), русское правописание и не нуждается в каких-то глобальных изменениях. Наша орфография сложна, но разумна, стройна и логична. В ее основу положен фонемный принцип, суть которого заключается в следующем: каждая морфема (корень, приставка, суффикс) пишется по возможности одинаково, несмотря на то что ее произношение в разных позиционных условиях может быть разным. Мы произносим [дуп], но пишем дуб, т. к. в этом слове тот же корень, что и в слове дубы; произносим [з]делать, но пишем сделать, т. к. в этом слове та же приставка, что и в слове спрыгнуть и т. п. Фонемному, или морфологическому, принципу отвечает 96 % написаний. И лишь 4 % – это разного рода исключения. Они обусловлены традициями русского письма. Мы пишем лестница, хотя могли бы писать лезтница (как лезть) и лесница (почему бы не проверить словом лесенка?). И при написании слова разыскивать не действует проверка словом розыск. Здесь свое правило: в приставках раз-/роз- под ударением встречается только о, без ударения – только а. Кстати, и из этого «неправильного» правила было исключение: слово разыскной предписывалось писать через о, и недавнее устранение этого странного исключения тоже вызвало жаркие споры... Можно было бы, конечно, ликвидировать все традиционные написания, подвести их под фонемный принцип, но... зачем? Это будет реформа беспощадная и бессмысленная: мы потеряем многие написания, в которых запечатлелась история русского языка, а кроме того, даже устранение этих 4 % исключений вызовет колоссальный взрыв в обществе. Незначительную их часть уже предлагалось ликвидировать в 1964 году (например, писать жолтый, жолудь), но эти предложения были с негодованием отвергнуты обществом.

И все-таки небольшие изменения в правописании неизбежны. Именно небольшие изменения, а не революции и не «реформа языка», которой так пугали общество журналисты. Сейчас официально действуют «Правила русской орфографии и пунктуации», принятые в 1956 году. Давно очевидно, что они устарели (представьте, что сейчас действовали бы Правила дорожного движения, принятые в 1956 году). Некоторые орфографические правила (о написании н/нн в прилагательных и причастиях, о слитном и раздельном написании сложных прилагательных и др.) ставят в тупик даже самых грамотных людей, не говоря уже о тех, кто только начинает изучать русский язык. Написание многих слов, часто встречающихся в современной речи, не регламентируется «Правилами»: 50 лет назад этих слов не существовало. Именно поэтому Орфографической комиссией РАН несколько лет велась работа над переизданием правил правописания с внесением актуальных для современной письменной речи изменений и дополнений. По экстралингвистическим причинам (в первую очередь – из-за негативной реакции общества на некоторые предлагавшиеся изменения) эта работа была приостановлена. Остается надеяться, что в ближайшие годы она будет доведена до конца. Создание и официальное утверждение нового свода правил русского правописания – это не прихоть лингвистов, а веление времени.

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

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