Правилен второй вариант. Поскольку в этом случае внутри вставной конструкции находится вставная конструкция, каждую из них следует закрыть отдельной скобкой.

Да, такой вариант возможен. Вставная конструкция выделяется с помощью скобок или тире. По правилам в тексте вставной конструкции сохраняются все необходимые для нее знаки: запятая, восклицательный и вопросительный знаки, многоточие, двоеточие.

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

Сравним случаи иного рода, которые приводятся, например, в примечаниях к параграфу 26.2 справочника по пунктуации Д. Э. Розенталя: Он посмотрел на пепелище, которое окружало его, — какой ужас! — и руки бессильно опустились у него — запятая закрывает придаточную часть сложноподчиненного предложения; Он встал и, прихрамывая — он был на протезе, — подошёл к окну (Кав.) — вставное предложение примыкает к предшествующему деепричастию, и запятая ставится после всей этой конструкции; Я забрался в угол, в кожаное кресло, такое большое, что в нём можно было лежать, — дедушка всегда хвастался, называя его креслом князя Грузинского, — забрался и смотрел, как скучно веселятся большие (М. Г.) — запятая перед первым тире закрывает предшествующую придаточную часть, а запятая перед вторым тире закрывает деепричастный оборот в самой вставной конструкции.

Мне всегда везёт с ними — это отдельное предложение, грамматически не связанное с остальными частями высказывания (они образуют сложноподчиненное предложение Я договорился с подрядчиками, чтобы остатками асфальта залатали ямы). Иначе говоря, это вставная конструкция. Наиболее уместны в таком случае скобки: Я договорился с подрядчиками (мне всегда везёт с ними), чтобы остатками асфальта залатали ямы.

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