This problem is captivating.

The more I think about it the more it drives me close to your approach: Recursively checking if the parent writes to the pseudo terminal master.

Maybe you can swap the readlink part with an `lsof /dev/ptmx | grep " $pid "`, instead of going through every processes opened file descriptors you go through the file descriptors of ptmx and check if it's there.
Or then you could also do `lsof -p $pid | grep '/dev/ptmx'`
Then continue the recursion.

I'm still sceptical of the edge cases, namely the sshd, login, etc..
There ought to be more than that.

sshd holds a file descriptor to /dev/ptmx, it's the endpoint in that case.
Let's say you have something else that is the "endpoint" and isn't a terminal but with our way it'll be listed as a terminal.
We need other features specific to a terminal.
If we remove the console, maybe we could presuppose the terminal is running in a graphical session.
But then again, maybe ssh could be thought of as a terminal.

I tried with a terminal multiplexer, they lead back to the right terminal, so no issues on that part.