Orphaned MySQL privileges

I have discovered that some of the MySQL instances which I administer have orphaned privileges for users that do not exist. The user no longer has an entry in MySQL user table but for whatever reason there are privileges in the other mysql.* tables for these non-existent user. It is not clear to me how the privileges got into this state. Maybe someone deleted the user directly from the MySQL user table and didn't use the DROP USER command.

Here is the query I wrote (partly based on the MySQL audit query) to find these orphaned  privileges.

(SELECT @@hostname as 'hostname', CONCAT("'",`user`,"'",'@',"'",`host`,"'") as 'credentials', 'database' as 'priv_level', db as 'object', TRIM(TRAILING ',' FROM(RTRIM(CONCAT(
IF(md.Select_priv = 'Y', 'Select, ', ''),
IF(md.Insert_priv = 'Y', 'Insert, ', ''),
IF(md.Update_priv = 'Y', 'Update, ', ''),
IF(md.Delete_priv = 'Y', 'Delete, ', ''),
IF(md.Create_priv = 'Y', 'Create, ', ''),
IF(md.Drop_priv = 'Y', 'Drop, ', ''),
IF(md.Grant_priv = 'Y', 'Grant, ', ''),
IF(md.References_priv = 'Y', 'References, ', ''),
IF(md.Index_priv = 'Y', 'Index, ', ''),
IF(md.Alter_priv = 'Y', 'Alter, ', ''),
IF(md.Create_tmp_table_priv = 'Y', 'CREATE TEMPORARY TABLES, ', ''),
IF(md.Lock_tables_priv = 'Y', 'LOCK TABLES, ', ''),
IF(md.Create_view_priv = 'Y', 'CREATE VIEW, ', ''),
IF(md.Show_view_priv = 'Y', 'SHOW VIEW, ', ''),
IF(md.Create_routine_priv = 'Y', 'CREATE ROUTINE, ', ''),
IF(md.Alter_routine_priv = 'Y', 'ALTER ROUTINE, ', ''),
IF(md.Execute_priv = 'Y', 'Execute, ', ''),
IF(md.Event_priv = 'Y', 'Event, ', ''),
IF(md.Trigger_priv = 'Y', 'Trigger, ', '')
)))) as 'Privileges'
FROM mysql.db md
WHERE CONCAT("'",`user`,"'",'@',"'",`host`,"'") NOT IN (SELECT DISTINCT CONCAT("'",`user`,"'",'@',"'",`host`,"'") FROM mysql.user)
)
UNION ALL
(SELECT @@hostname as 'hostname', CONCAT("'",`user`,"'",'@',"'",`host`,"'") as 'credentials', 'table' as 'priv_level', table_name as 'object', table_priv as 'Privileges'
FROM mysql.tables_priv mt
WHERE CONCAT("'",`user`,"'",'@',"'",`host`,"'") NOT IN (SELECT DISTINCT CONCAT("'",`user`,"'",'@',"'",`host`,"'") FROM mysql.user)
)
UNION ALL
(SELECT @@hostname as 'hostname', CONCAT("'",`user`,"'",'@',"'",`host`,"'") as 'credentials', 'column' as 'priv_level', column_name as 'object', column_priv as 'Privileges'
FROM mysql.columns_priv mvc
WHERE CONCAT("'",`user`,"'",'@',"'",`host`,"'") NOT IN (SELECT DISTINCT CONCAT("'",`user`,"'",'@',"'",`host`,"'") FROM mysql.user)
)
UNION ALL
(SELECT @@hostname as 'hostname', CONCAT("'",`user`,"'",'@',"'",`host`,"'") as 'credentials', 'procs' as 'priv_level', routine_name as 'object', proc_priv as 'Privileges'
FROM mysql.procs_priv mf
WHERE CONCAT("'",`user`,"'",'@',"'",`host`,"'") NOT IN (SELECT DISTINCT CONCAT("'",`user`,"'",'@',"'",`host`,"'") FROM mysql.user)
);

I've seen on other blogs queries like this:

SELECT host, db, user
FROM
     information_schema.SCHEMATA right join
     mysql.db ON (SCHEMATA.SCHEMA_NAME=db.Db)
WHERE SCHEMA_NAME is null;

That query will help to find privileges for databases that do not exist anymore or never existed but it doesn't work so well in my case. We use wildcards in the GRANT statements a lot because we have thousands of databases on each server with the database has the same prefix. When I run the above query it returns results for the wildcard entries but those are not actually orphaned privileges.