O comando tail tem que ler o arquivo inteiro para calcular as últimas dez linhas. Ele determina linhas procurando por caracteres de nova linha. Então, está lendo o arquivo procurando por strings fixas.
Seu grep, por outro lado, está lendo todo o arquivo procurando por uma string fixa. Parece quase a mesma coisa. Concedido, o grep é um pouco mais complexo, mas eu aposto a sobrecarga de bifurcar um novo processo e configurar os pipes é mais do que a sobrecarga do grep. Você pode, no entanto, acelerar um pouco o grep dizendo que seu padrão é uma string fixa em vez de um regexp. Para fazer isso, especifique a opção "-F" para grep (ou use fgrep). Se você tem o GNU grep, você provavelmente também pode usar o --mmap para acelerar as coisas.
Dê uma chance a grep -rnl * --mmap -F -e "Ai9LbaFz7lC13SwzDxAYT72vwA"
e veja se ela é tão rápida ou mais rápida do que a sua solução com a cauda. :)
A precisão da varredura somente do grep é outra questão, no entanto, já que isso ainda não está validando que a correspondência está nas últimas 10 linhas do arquivo. Mas eu espero encobrir essa parte sugerindo o uso de um comando de pós-processamento para contar as linhas em arquivos correspondentes ou algo assim. ;)