Yes, search is an issue. web.archive.org itself is not indexed in any of the search engines. Instead, it is a site for recovering broken links (I go to Rootsweb or, say, the Norwegian genealogical forum forum.arkivverket.no, I find a discussion with a link to further information I would like to see, I find the link is broken, I then go to web.archive.org and input the broken URL in the Wayback Machine to see if a version of it was archived).
And this is apparently how the German Wikipedia works - it has a bot that, whenever it finds a broken link in the references or sources in a Wikipedia page, it then goes to the Wayback Machine, checks whether a version there was saved, and if so then places the link from web.archive.org on the Wikipedia page (for an example, if you don't mind German, see footnote 2 in this German Wikipedia article).
So yes, there is a trade-off between permanence and discoverability here. In order to make a page that has been archived discoverable, you have to discuss it elsewhere. For example, Tore Vigerust's work these days can't be found directly on Google anymore, it can be found only because other people discussed it both on Rootsweb and the Norwegian genealogy forum and probably elsewhere as well and provided links there. But because links to it were spread liberally across the internet, his work can now be recovered even after his website disappeared when his estate ceased paying for it.
So, if you want something with reasonable assurance of permanence on the net (at least as long as the internet itself exists), one way of doing it is to create an archived version and then making sure that links to it are liberally spread around. There are probably other ways of getting permanence as well.