Lotus 123 and WordPerfect once had market domination, but that didn't stop Microsoft from marginalizing them. Just leveraging Windows to make them a bit less convenient to use and maintain did the job in a few years.

PDF is much used now because Microsoft has no equivalent. I already see about as many .DOC files on the Internet as I do PDFs even though .DOC isn't equivalent. Whether PDF is supplanted depends on the acceptance of Longhorn and Microsoft's Rights Server. If Linux has captured a good portion of the desktop before Microsoft can get Longhorn rolling, PDF will survive.

Search engines are a much easier target. Microsoft hasn't tried at all to push them aside yet because their own search technology is 3rd party, but that's changing. Once Microsoft no longer depends on outside search engines you will see the playing field start to tilt.