Since search engines are queried with a URL with a parameter for the search term, browsers could simply allow "power users" to enter a custom URL. Voilà — support for every imaginable search engine and they can still make their billion dollar deals for providing default search engines. That's how Firefox does it.