buridan, try setting Enable Caching? to No, for the template where the search form tag is located. You can use Edit Preferences for the template, from the Template Manager.
If this solves your problem, but you need the caching for speed on the overall template, move the search form tag to an embed, and disable caching just for that tag.
This keeps coming up; it and other search issues were pretty well gone over in the forum, with a bug report attached. Direct to your problem, see here.
Regards,
Clive
p.s. be sure to clear all EE caching, and you probably need the deinstall Seach Module/reinstall step once as well, before testing this workaround, so that you see good results without interference from prior problems.