the UI might start to get a bit out of control, especially in search windows

Ah but this can work!

Search won't need Blend because it only ever returns ONE song. I would even argue that Append and Queue are unnecessary as search modes because, if I'm searching, I want to hear it NOW. And I bet no one ever really wants to Replace from search. So, there you have it - one mode for search: Insert.

Blend would only show up in Playlist menu if Shuffle is on. There is no need for "Insert" since this behaves as Queue right now anyway. But, if you want to add a true Insert, that would be cool too.