Как да изтрия всички осиротели записи в MySQL?

Можете да използвате not exists :

delete from user
where not exists (select * from message m where m.userid = user.id)
      and not exists (select * from archivedMessage am where am.userid = user.id)