No final, eu fui com alguns dos métodos dos comentários. Tirar o rabo do loop principal permitiu simplificar ainda mais a lógica: o que acabei fazendo foi algo como:
while true
echo "Starting the application"
run_application
echo "Application exited - checking logs for KEY"
if ! tail -qn 100 logs/* | grep -q "KEY"
then
echo "Failed without KEY in the logs - exiting"
break
fi
echo "Failed with KEY in the logs - restarting"
done