I am having the same problem and at the moment I have determined that there is an internal redirect that is happening that is causing the GET variable to have it’s spaces stripped.
I have a local copy that works fine. It uses permalinks. The exact hosted copy is having the problem. Using firebug I can see on the hosted copy there is a request for: GET /search/?term=this+that
Then there is a second request: GET /search/?term=thisthat
right after the first request.
Locally this doesn’t happen.
I’m still investigating.