+1 to this, although if the devs are really against the idea, making legends re-catchable is still much better than nothing.
You are actually worse off. Just because it isn't game breaking doesn't mean you aren't at a disadvantage. Every other pokemon in the game has a method of re-catching except these. Also celebi is very strong in pvp. It functions as a baton passer or bulky support pokemon with utility moves such as stealth rocks, heal bell, thunder wave, etc.
As you said, the best idea draw from your point is ban legend from pvp, so you will not say "Putting unlucky players at a permanent disadvantage in pvp is a bad idea" Everyone then will fair then. And bear in mind that pvp not belong to only 1 pokemon also, it is the strategy and also how to deal with team :/
Legendaries add more options for team building and fill some unique roles in the metagame. I would rather have them than not have them, especially when the current problem with legendaries in pvp is easily fixable.