Lo que estás tratando de hacer suena peligroso, ya que no es el uso previsto de AUTO_INCREMENT .
Si realmente desea encontrar el valor clave más bajo sin usar, no use AUTO_INCREMENT en absoluto, y administre sus claves manualmente. Sin embargo, esta NO es una práctica recomendada.
Dé un paso atrás y pregunte "¿por qué necesita reciclar valores clave? " Hacer INT sin firmar (o BIGINT ) no proporciona un espacio clave lo suficientemente grande?
¿De verdad vas a tener más de 18,446,744,073,709,551,615
registros únicos a lo largo de la vigencia de su aplicación?