Esattamente, come ha detto brodik, tu stai cercando "2222222" (sette 2), che dalla stampa dell'array che proponi non c'è, c'è invece "22222222222" (undici 2) quindi array_search() ti ritorna false che equivale a 0 e se non fai controlli fai danno come in questo caso, perché vai a cancellare un elemento che non vorresti cancellare.

Mettici un if che controlli se $key !== false, non solo !=, così sei sicuro se hai 0 o false e se non hai false procedi alla cancellazione, altrimenti no. In questo caso cadresti nella condizione "altrimenti no" e non cancelleresti per sbaglio il primo elemento.