Probaste ejecutar un
reset() antes del array_search()? Creo que el problema es que el puntero interno de los array queda donde lo dejaste la ultima vez y cuando volves a buscar ese ya no lo tiene encuenta. Prueba ejecutar reset() y me cuentas.
Saludos.