If you search a protected page using Special:Search and you're not a sysop, you won't see "This page doesn't exist, you can create it". That's not an isssue as long as the message isn't customized by the wiki.
For instance, Czech Wikipedia adds a link to Wiktionary, and also a link to whatlinkshere.
Maybe we should add a searchmenu-new-append message, empty by default, that would allow wiki owners to add always-displayed message, even if the page is protected? What do you think?