Super Cache is refreshing too frequently!

Donncha (or anyone familiar with Super Cache),

I just installed super cache for my site(http://www.home-designing.com/) and noticed something really odd. Everytime a new user visits the site, he is served a dynamic page that is just supercached. For example I had asked a friend who is a first time visitor to check out a page and the following code is generated:

<!-- Dynamic page generated in 0.451 seconds. -->
<!-- Cached page generated by WP-Super-Cache on 2009-04-23 15:45:21 -->

However when I ask another first time viewer to visit from another location, 2 mins later this is what he gets

<!-- Dynamic page generated in 0.528 seconds. -->
<!-- Cached page generated by WP-Super-Cache on 2009-04-23 15:47:32 -->

After their first load, both the users are served from the cache. That is, the timestamp of the page(though different for each) remains constant for them.

Also, I checked if static files were getting placed in the folder and found they are.

Why does this happen? It takes out the very purpose of the plugin if the pages are being dynamically generated each time.

Here are some other details:

Expiry time: 3600 seconds

Cache Contents

WP-Cache (2.64MB)
79 Cached Pages
0 Expired Pages

WP-Super-Cache (5.15MB)
85 Cached Pages
0 Expired Pages

Garbage Collection
Last: 2009-04-23 09:49:01
Next: 2009-04-23 09:59:01

* I could see another similar thread posted about this: http://wordpress.org/support/topic/195133

which suggested clearing cookies and disabling firewalls. Both didn’t work for me.

Any help would be appreciated!