It seems that using mod_rewrite to set or modify the query string can corrupt it. One case where it certainly fails is if the URL has %2B (a urlencoded "+" character) in it.
As a demonstration, try searching for the string "alice + bob". You can see on http://drupal.org/search/node/alice+%2B+bob that the rewrite rules change the %2B to a space, while on http://drupal.org/?q=search/node/alice+%2B+bob it work correctly without clean URLs.
The reason I am posting it here as a warning and not as a bug report is that it's not a Drupal issue, but a mod_rewrite issue. (It would be worth a bug report for mod_rewrite, but they have such bug reporting guidelines that require a few hours' work to follow...)