It's possible that Google is telling the truth. The FTC is paying close attention, especially after the settlements in the Buzz and Safari cookie incidents. Deceptive data collection and use practices--like lying about having location data--would certainly trigger FTC enforcement.

They are probably not explicitly lying about what information they retain. If they say they deleted it, well, it's probably at least inaccessible to production systems.