Isn't google providing a lot of heavy lifting for wikipedia, by "figuring out" what I want and taking me there.

Wiki just on itself, where you need to browse inside to get where you need won't work. Now you need to find the right node in the graph that connects to your information.

I feel the same way about Stack Overflow. I rarely search for the answer to my question inside SO, instead google takes me to the relevant page.

So what companies seem to need is documentation in any format, hierarchy or graph, plus a really, really good search engine over it.

Links aren't used for searching, they're used for expanding knowledge on a topic you're already investigating. A personal example: I had to update our metrics infrastructure so I read the existing documentation to understand the way it is done today, and there was a link to our metrics naming spec. I wasn't going to need it but it was still interesting to understand what the conventions are and potentially updating them.

We're using the Atlassian wiki, for which I find search to be very bad so we kind of _have_ to work with links.

Hard agree. Finding information on SO has always been much easier for me by asking Google to search there than by using the local search bad.