@AndrewLeach - That would make sense if a user can see their own deleted questions even without much rep. Early on, one of my answers was deleted, and when I tried to find it, all I saw was Alice and the notice that it didn't exist. Later, with more rep, I stumbled across it.
I know you're feeling no-nonsensy with Anonymous, but they can't learn if they can't see it. Might it be worth knowing for certain if they can see it?