Replacing search functionality

I’m trying to create a plugin to replace the default search functionality of wordpress with my own. Is this possible?

I thought of just having my own plugin query_posts using my logic, and then include search.php and call it all from the template_redirect action. But AFAIK, the original search functionality will still execute before mine, even if I do get the results I want. I don’t want that to happen.

If I change the search query from ?s=search+term to ?find=search+term and do the same, it solves the above problem, but now, is_search() doesn’t return true, which causes major problems down the line.
Also I have to change the search form in my theme files (not the end of the world since I’m only developing the plugin for my own site)

Is there any way of using my search logic, but making word-press believe it’s executing a search? (So is_search() will be true, etc.)