It is possible to find all posts by a deleted user in SEDE if we know UserId, see here: Is it possible to know the questions and answers by a no longer user?
We can also check all comments under those posts and, more specifically, those posts which contain comment replies ("@username").
It is mostly guesswork, but if some username repeats there quite often, it might be a reasonable guess that it was username of that user.
Here is a test: Comment replies under posts by a deleted user. I have to admit that I would not be able to guess this users' name from those result. (Indeed, the poster is notified even without including "@username" so it's quite likely that it is often omitted.)
Perhaps there is a slightly bigger change that we find something if we look at comments by a deleted user. Here is what I have tried: Possible comment replies to a deleted users.
It's possible that somebody would be change the query in such way that it collects all strings which start with "@" from those results, but that goes beyond my SQL skills.