Just gong back to the original question I am a little confused.
You said at the top of this thread that the search always results in 0 (zero) finds. Then later you say that it always results in a 404 page. These are very different results with very different reasons.
If it is indeed a 404 on every search then either – s I suggested – there is a url conflict with another plugin – or, and this is actually probably more likely – your host is running mod_security on your server as Steve suggested.
I would say the first thing to do is ask your host about this and if they have put mod_security in place ask if it can be removed or if the search url vars can be white-listed. Most hosts will usually accommodate this request.