The “Secure Forms” option inserts a “security hash” in your page (and the database) when you view it. Then, when you submit a form (say, the search form), pMachine compares the submitted security hash to the one stored in the database. If they match then the form is accepted. If they don’t match then you get the error message you mentioned.
Now, the other thing here is that the security hashes are only valid for a limited time (2 hours, I believe). If you load your page, leave it sitting there for a few hours, and then try a search, you’ll be submitting a security hash that has expired. I run into that all the time since I leave my own site open in a browser window. To fix it, simply refresh your page before you enter the search terms and submit. Refreshing the page will generate a new security hash and you’ll be good to go.