The console owners need to handle this like Valve and most other PC stores do: If money changed hands, a game will never be removed from a player's account. Not even if the publisher *really* wants it gone.
Yeah, absolutely. That's the only way to have trust for the store and service. Steam has near 15 years of proving this consistently - though let me highlight something a shitty pub / developer can do, vs what a great pub / dev would do
1 - Rockstar - San Andreas - iirc they pulled the game, and naturally owners can still redownload, but when they brought it back, they pulled out the music that was causing an issue for both old and new users. This was completely unnecessary, lazy and not something Valve did anything about - mostly since its fairly easy to mod back in, but it is a problem nonetheless. What the dev should have done, is leave the depot as it was for those owners. They could make a seperate depot for new users, which would have been best for all.
2 - Mafia 1 - game was pulled years ago, all users could still play it. When the dev / pub years later brought back a remaster, they updated the game for all users - BUT, made a seperate DLC exclusive to the original owners, containing the entire unaltered music. That's how you do it!
For all the remasters where games have been pulled, so far on Steam, I have all of them still available to me - or received the new version free - which is a simple good gesture.