The tail command has to read the entire file in order to calculate the last ten lines. It determines lines by looking for newline characters. So, it's reading the file looking for fixed strings.
Your grep, on the other hand, is reading the whole file looking for a fixed string. Sounds like pretty much the same thing. Granted, the grep is a tad more complex, but I'll bet the overhead of forking a new process and setting up the pipes is more than the grep overhead. You can, however, speed up grep a little by telling it that your pattern is a fixed string rather than a regexp. To do that, specify the "-F" option to grep (or use fgrep). If you have GNU grep, you can probably also use --mmap to speed things up.
Give grep -rnl * --mmap -F -e "Ai9LbaFz7lC13SwzDxAYT72vwA" a try and see if perhaps it's as fast or faster than your solution with tail. :)
Accuracy of the grep-only scan is another question, though, since this still isn't validating that the match is in the last 10 lines of the file. But I'm hoping to gloss over that part by suggesting the use of a post-processing command to count the lines in matching files or something. ;)