Может и может быть — вводные слова, поэтому в обоих предложениях нужна запятая.

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

Оба варианта корректны. Предложение можно рассматривать как простое, с подлежащим собрать и сказуемым задача (между ними необходимо тире), а можно — как бессоюзное сложное, первая часть которого представляет собой номинативное предложение (поскольку во второй части содержится объяснение, перед ней нужно двоеточие). 

Так о чем спорить? Ведь собеседники в итоге поняли, что именно каждый из них имел в виду.

Теперь ответить на этот вопрос можно не так, как мы отвечали раньше. В 2024 г. в академическом орфографическом словаре, размещенном на ресурсе «Академос» Института русского языка им. В. В. Виноградова РАН, разработаны новые способы подачи названий, которые употребляются на письме в двух формах – официальной и неофициальной. Официальная форма названия определяется в соответствии с юридической фиксацией (в Конституции Российской Федерации, федеральном законе, положении об организации, уставе) и обозначается пометой офиц. (официальное).

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

Теперь «Академос» фиксирует:

Вое́нно-Морско́й Фло́т (в Вооруженных силах Российской Федерации, офиц.) и Вое́нно-морско́й фло́т (в Российской Федерации) 

вое́нно-морско́й фло́т (у страны́ си́льный вое́нно-морско́й фло́т) 

Вое́нно-Морско́й Фло́т СССР

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

Данное правило здесь неприменимо, т. к. прилагательное доступен имеет полную форму: доступный. В приведенном Вами примере возможно и слитное, и раздельное написание.