¿Cómo hacer cumplir la integridad referencial en la herencia de tabla única?

Lo que puede hacer es implementar disparadores en sus Users y Team tablas que se ejecutan cada vez que se eliminan filas de:

Tabla de usuarios:

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 ;

Mesa de equipo:

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 ;

Lo que harán estos disparadores es cada vez que se elimine un registro de una de estas tablas, un DELETE la operación se ejecutará automáticamente en las Playlists tabla usando el id que está a punto de eliminarse (a través de una unión interna).

He probado esto y funciona muy bien.