It all boils down to risk. Yes, there is some data that companies are required to keep for N years due to auditing, etc. That's unavoidable. But there comes a point where keeping data (especially personal information that is usually covered by numerous laws and 200-page policies from bodies such as the credit card industry) becomes a liability. Companies typically don't like liabilities, and therefor delete it.

Now, there are data that a company might consider keeping because the income generated by keeping it outweighs the risk associated by mishandling it. And you're right, there's no way of knowing what Google considers this to be. But that was my original point- if you don't trust Google to delete your history when you ask, then why do you trust them to not keep it in the first place when you opt-out?