Thank-you very much for your help, I found the problem and now the search works.
There was a problem with my search form's action which was still pointing to "index.php?p=search" even if "mod_rewrite" was enabled. I added a check to change the action depending on whether or not "mod_rewrite" is enabled and it now works as expected.
Thanks again for your help