incrediBILL - 8:15 pm on Aug 28, 2008 (gmt 0)

Mystery solved!

It's the data center that makes the difference.

If you get cache from here, no AdSense ads display!
http://209.85.141.104/search?q=cache:

If you get cache from here, you get AdSense ads!
http://74.125.95.104/search?q=cache:

So cut & paste your cache query to either of the links above and you should see the different behavior depending on the cache server.

No clue why, but at least we know where it happens now.

Thanks to purplecape for the clue in helping figure this out ;)