Como impor a integridade referencial na herança de tabela única?

O que você pode fazer é implementar gatilhos em seus Users e Team tabelas que são executadas sempre que as linhas são excluídas de:

Tabela de usuários:

DELIMITER $$
CREATE TRIGGER user_playlist_delete 
BEFORE DELETE ON User FOR EACH ROW
BEGIN
    DELETE a FROM Playlist a
    INNER JOIN UserPlaylist b ON a.id = b.id AND b.userId = OLD.id;
END$$
DELIMITER ;

Tabela da equipe:

DELIMITER $$
CREATE TRIGGER team_playlist_delete 
BEFORE DELETE ON Team FOR EACH ROW
BEGIN
    DELETE a FROM Playlist a
    INNER JOIN TeamPlaylist b ON a.id = b.id AND b.teamId = OLD.id;
END$$
DELIMITER ;

O que esses gatilhos farão é cada vez que um registro for excluído de uma dessas tabelas, um DELETE a operação será executada automaticamente nas Playlists tabela usando o id que está prestes a ser excluído (por meio de uma junção interna).

Eu testei isso e funciona muito bem.