Si eliminas el cliente también eliminas el número de expediente, debo entender que ese número queda disponible, verdad?
Tendrías que hacer a la tabla solamente en ese campo, y al momento de recoger los valores comparar cada uno de ellos con su anterior+1, si son iguales entonces sigue comparando sino es porque esta libre. Luego escoges uno de esos valores el mayor o menor (el que quieras y le sumas u restas 1 dependiendo de cual elijas).
Y así tienes el que esta disponible, si quieres que te salga el primero que este disponible aumentas un ORDER BY en la consulta y listo.
Al menos eso es lo que yo haría
Espero pueda servirte.