So would this simply work if the Link component from nextjs wasn't used?
The problem is logging out on a GET request, as discussed in current top comment. It's just semantically incorrect and many tools will (correctly) assume GET requests don't have side-effects (in HTTP's terms, it's a safe method).
E.g. it's very easy to have a GET request cached by mistake (and I've seen some faulty proxies do that, completely ignoring the upstream cache-control).
This is not a problem on Next or its Link component. It's on op's code (and maybe auth0-nextjs allowing logout on GET requests).