Irrecoverable Error "Could not find valid Key" when using Find Contacts with empty values

1. Click "Find Contacts" from Dashboard
2. Leave all fields blank and click "Search"
3. You'll see an unrecoverable error "Could not find valid Key" right away.

I did a trace... it seems to be related to session.

When I clicked "Search", it goes to an intermediate CiviCRM handler which then redirects to the result page via header().
In the result page, the session handler seems to set $_SESSION['CiviCRM'] to NULL right after session_start().
Thus, CiviCRM could not find the old key associated with the user/controller and tries to create a new one. This causes a mismatch with the key embedded in the search form.

I inserted an error_log to print out the session variable in session_read() [includes/session.inc], it seems to read the session correctly (i.e., $_SESSION['CiviCRM'] is not empty).

My platform is Solaris 10, Apache 2.2.4, php 5.2.1

My session config is (They are all default):

[Session]
session.save_handler = files
;session.save_path = "/tmp"

; Whether to use cookies.
session.use_cookies = 1
;session.cookie_secure =
; session.use_only_cookies = 1
session.name = PHPSESSID
session.auto_start = 0
session.cookie_lifetime = 0
session.cookie_path = /
session.cookie_domain =
session.cookie_httponly =
session.serialize_handler = php
session.gc_probability = 1
session.gc_divisor = 1000
session.gc_maxlifetime = 1440
session.bug_compat_42 = 0
session.bug_compat_warn = 1
session.referer_check =
session.entropy_length = 0
session.entropy_file =
;session.entropy_length = 16
;session.entropy_file = /dev/urandom
session.cache_limiter = nocache
session.cache_expire = 180
session.use_trans_sid = 0
session.hash_function = 0
session.hash_bits_per_character = 5