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

В этом предложении тире не нужно, так как между подлежащим патрулирование и именным сказуемым что-то вроде наказания находится дополнение для них (см. пункт 7 параграфа 15 справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина). Обратите внимание, что в неофициальном географическом названии с прописной буквы пишется только первое слово, само это название в кавычки не заключается: Видимо, патрулирование Ржавого пояса для них что-то вроде наказания.

Правильно: во Фрунзенском районе. Перед формами слов, начинающимися сочетаниями «в, ф + согласная», последовательно выступает предлог во (ср.: во вторник, во Франции). Написание в данном случае отражает произношение.

Запятую в таких случаях рекомендуется не ставить, т. к. слова не позднее / позже чем не используются для сравнения или сопоставления, их можно заменить обычными наречными выражениями самое позднее, в крайнем случае, ср: уведомить самое позднее за день.

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

Это не контаминация.

Правильно: (жить) на Украине.

Да, такие сочетания называют мёртвыми метафорами. См.: 

Ричардс, Ай­вор  А. Фило­со­фия ри­то­ри­ки / А. А. Ричардс ; пер. с англ. Р. И Ро­зи­ной // Тео­рия ме­та­фо­ры / вступ. ст., сост. Н. Д. Ар­утю­но­вой ; пер. под ред. Н. Д. Ар­утю­но­вой и М. А. Жу­рин­ской. – М., 1990. – С. 44–67. 

"Разрешите мне теперь привести пример простейшей, всем знакомой метафоры ножка стола. Мы называем эту метафору мертвой, но она очень легко оживает. Чем отличается она от использования слова в прямом или буквальном значении в та­ком, например, выражении, как нога лошади*.
/* В английском языке, в отличие от русского, вместо двух слов ножка и нога есть лишь одно слово leg — Прим. перев./
Очевидное раз­личие состоит в том, что ножка стола обладает лишь несколькими признаками из числа тех, которыми наделена нога лошади. Нож­ки стола не ходят, они только поддерживают его. В подобных случаях мы называем общие признаки основой метафоры. В приведенном примере мы легко находим основу метафоры, но очень часто это оказывается невозможным. Метафора способна прекрасно работать и тогда, когда мы не можем судить о том, как она работает или что лежит в основе переноса.
<…> Вернемся снова к примеру со словом нога. Мы замечаем, что даже здесь границу между буквальным и метафорическим употреблением слова нельзя считать полностью стабильной или постоянной. В каких случаях это слово используется буквально? У лошади есть ноги в буквальном смысле этого слова, так же, как и у паука. Но что сказать о шимпанзе? Сколько у него ног — две или четыре? А морская звезда? Что у нее — руки, ноги или не то и не другое? А если у человека деревянная нога, что имеется в виду — нога в метафорическом или в буквальном смысле? Можно ответить, что здесь сочетаются оба смысла. С одной точки зрения, слово нога используется в буквальном смысле, а с другой —в метафорическом. 
Слово может одновременно вы­ ступать в своем прямом и метафорическом значениях, так же как на основе этого слова может быть одновременно создано несколько метафор или же в одном значении сливаться несколь­ко. Этот тезис представляется нам крайне важным, поскольку очень часто неверные теории возникают из-за убеждения в том, что, если слово функционирует каким-то одним образом, оно не может в то же самое время функционировать по-другому и иметь одновременно разные значения.

Слово республика действительно восходит к латинскому языку (от rēs рūbliса, букв. «общественное дело»). Таким образом, буква «с» в этом слове – из латыни, она не была добавлена в русском языке. А вот в западноевропейских языках она и правда пропала: англ. translation>republic, нем. translation>Republik, фр. translation>république, исп. translation>república, итальянцы же «компенсировали» утраченную «с» второй буквой b: translation>repubblica.

По-видимому, «с» утратилась в Средние века в результате фонетических изменений в романских языках. По крайней мере, англичане уже заимствовали это слово из французского языка без буквы «с». Вот цитата из вебстеровского словаря английского языка о происхождении английского слова republic: «French république, from Middle French republique, from Latin respublica».

Под освоенностью в данном случае понимается то, что название является привычным для носителя языка вследствие более или менее частого употребления в устной и письменной речи; четких критериев (дата заимствования, количество словоупотреблений и др.) нет.  Например, такие названия, как Вевак, Наматанай, Маданг (Папуа – Новая Гвинея), вряд ли известны большому числу носителей языка, поэтому при употреблении с родовым словом город их целесообразно не склонять. А такие названия, как Казань  и Уренгой, давно употребляются в русском языке, они известны (или, по крайней мере, должны быть известны) большинству говорящих и пишущих по-русски, поэтому их можно назвать освоенными русским языком.

Что касается названия нашей планеты, то оно не склоняется при употреблении с родовым словом. Правильно: на Земле, но: на планете Земля.