Search form block not functioning in all civicrm pages

[vences]

I'm using drupal 7, and set a search form block in website header. In other pages, the search form works well. Only when I try to use search in all civicrm page, it doesn't submit to search form, but submit to the same civicrm page and shows error like below:

Sorry but we are not able to provide this at the moment.
We can't load the requested web page. This page requires cookies to be enabled in your browser settings. Please check this setting and enable cookies (if they are not enabled). Then try again. If this error persists, contact the site administrator for assistance.

Site Administrators: This error may indicate that users are accessing this page using a domain or URL other than the configured Base URL. EXAMPLE: Base URL is http://example.org, but some users are accessing the page via http://www.example.org or a domain alias like http://myotherexample.org.

Error type: Could not find a valid session key.

The civicrm pages includes event, contribution, report, civicrm admin, everything related to civicrm.

Is there anything which I missed out in configuration which leads to this error?

[Michael McAndrew]

Since you didn't address it explicitly in your post, I have to ask, did you rule out the error message that is being displayed?

"Site Administrators: This error may indicate that users are accessing this page using a domain or URL other than the configured Base URL. EXAMPLE: Base URL is http://example.org, but some users are accessing the page via http://www.example.org or a domain alias like http://myotherexample.org."