If you read more closely, it's not enough to _have_ a header; the header must also indicate that cookies are not used for tracking.
The problem is, that indication is made with _lack_ of a particular token; and google includes a fake P3P header with no tokens in it. Thus, according to the protocol, google's header indicates that it does not use cookies for anything at all.
It's just plain wrong. The cookies can be used for tracking. You just need to tell what kind of tracking and what you do with that information.
http://news.ycombinator.com/item?id=3615381
The problem is, that indication is made with _lack_ of a particular token; and google includes a fake P3P header with no tokens in it. Thus, according to the protocol, google's header indicates that it does not use cookies for anything at all.