I haven't thought of every corner case but I would set up something like this:

You can track a user during a single session on a single site.

To track across multiple visits the user must set up an account of some sort.

To track across multiple sites the user must provide some kind of explicit permission.

Anonymize any session records that don't have this kind of permission.

That seems a little excessive, but the sentiment is good. Any personal data, including browser history, should not be stored without user consent.... Like a "track me" header field.