I did additional research.

It looks like it is not about Expire date. I created one simple PHP script to mimic the same headers to see if there will be any difference.

This is what I got:
***23/Feb/2011:16:35:56 +0100 MISS Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0 Expires: Thu, 19 Nov 1981 08:52:00 GMT "GET /test2.php HTTP/1.0" (200) "Wget/1.11.4 Red Hat modified"
***23/Feb/2011:16:35:57 +0100 HIT Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0 Expires: Thu, 19 Nov 1981 08:52:00 GMT "GET /test2.php HTTP/1.0" (200) "Wget/1.11.4 Red Hat modified"
***23/Feb/2011:16:36:02 +0100 MISS Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0 Expires: Thu, 19 Nov 1981 08:52:00 GMT "GET /opensearch HTTP/1.0" (200) "Wget/1.11.4 Red Hat modified"
***23/Feb/2011:16:36:03 +0100 MISS Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0 Expires: Thu, 19 Nov 1981 08:52:00 GMT "GET /opensearch HTTP/1.0" (200) "Wget/1.11.4 Red Hat modified"

With same expire date, first request is cached and the second is not.
These are full headers:
Server: nginx/0.8.53
Date: Wed, 23 Feb 2011 15:35:56 GMT
Content-Type: text/html; charset=UTF-8
Connection: keep-alive
X-Powered-By: PHP/5.3.5
Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0
Expires: Thu, 19 Nov 1981 08:52:00 GMT
Pragma: no-cache
Content-Length: 23

HTTP/1.1 200 OK
Server: nginx/0.8.53
Date: Wed, 23 Feb 2011 15:36:02 GMT
Content-Type: text/xml; charset=UTF-8
Connection: keep-alive
X-Powered-By: PHP/5.3.5
Set-Cookie: SomeSessionId=nlt391qunv2prlpogjc6fne4o4; path=/; domain=.some.domain.com.
Expires: Thu, 19 Nov 1981 08:52:00 GMT
Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0
Pragma: no-cache
Content-Length: 1429

Only difference is that second request (the one that is not cached) had Set-Cookie, but I don't use cookie in proxy_cache_key.
proxy_cache_key "$host$request_uri";

What am I missing?

D