Currently for performance reasons (since 404s are not cached by varnish and bots sometimes mass request non-existent pages) we only show the moveddeleted message saying that a non-existent page was previously deleted, if the user is logged in or if the page was recently deleted.
However this misses editors who don't log in but still do edit. Well not perfect, we could capture this group by looking to see if a session currently exists (Which happens if the user had previously previewed a page this browsing session). (Using $this->getContext()->getRequest()->getSession()->isPersistent() )
Relavent code is includes/page/Article.php line 269