It should be the imperfective form: "даже если они долго БУДУТ ИСКАТЬ, Вадима они не найдут".
Why "БУДУТ ИСКАТЬ"?
(1) The process of searching for Vadim will be ONGOING and, probably REPEATED:
they will look here and there and everywhere;
(2) They will fail to find him, the main sentence implies that the process of search will be unsuccessful.