Take a search engine (e.g. Google), where user A can make searches without logging in with their account. The search engine collects, processes and stores, over time, a number of data about the user A, such as cookies identifiers, IP address, browsers fingerprint, and the search strings. I think all these are "Personal Data" according to GDPR (right?). How could user A exercise his right of access to these data? In particular:
how could user A compile such a SAR, given that the search engine has no identifiable information other than the cookie ID (something like "please supply the personal data you hold about me, identified by cookie ID X"?)
how could user A demonstrate he is the real owner of those data (and not someone else using the same device/connection)