MySQL command denied for DELETE with JOIN
I've finally tracked down the cause of the permissions issue I'm running into. It turns out that the problem was actually a bug in MySQL.

We're running our infrastructure on AWS Aurora which runs MySQL version 5.10. To set up for providing more information, I tried to recreate the problem locally in a docker container, using the latest version of MySQL (5.7.16). To my surprise, I couldn't reproduce this issue locally, which led me to believe the problem has to be with the difference in MySQL version.

Going through the MySQL version logs, I noticed that in MySQL version 5.6.27, a bug was fixed:


  DELETE could check privileges for the wrong database when table
  aliases were used. (Bug #20777016)


This sounded promising so I modified the query to not use aliases and sure enough, the permissions issues went away.