>I deleted my YouTube history just this week, but my homepage is full of music mixes that start with a song I definitely listened to that are supposedly "deleted" from my history

Consider clearing out session cookies, I am under the impression that your recommended videos are also using that as a source.

To me, Youtube and YT music are the same services in different shells, maybe the algorithm uses both (maybe it includes activites from other google products as well) to suggest them on the platform.