Your opinion is a fact, imo. Songs can't be deleted from playlists using REST, full stop. Songs-in-playlists are values, not identities, so they can't be resources. I see it as analogue to words in a text file. A REST client would have to construct the updated playlist value and PUT the whole thing to the playlist resource. So "delete song from playlist" is a function that could only exist in the client.
Search on the other hand is just search. I don't think REST vs RPC has much to say about it. The only issue would be location: URL vs method.