Basically, if a slug starts with xn--, it gets decoded as Punycode, if not, it's legacy.
If a page title has any Unicode characters in it, it gets encoded as Punycode, if not, it get encoded as it does now.
But there could be existing pages named with Unicode characters that are currently just getting stripped off. Need to game out that case.
So the scenario is: another page links to "Baseball Бита" and the page already exists with the slug "baseball-". However the Punycode slug for "baseball-бита" (space replaced with "-", case folded to lowercase) is "xn--baseball--8yhk8f9f".
So if we will keep compatibility, we need to search first for the old slug "baseball-", then if that fails, for "xn--baseball--8yhk8f9f".