The definitions of "personal information" and "valid reason" are, fortunately, not exhaustively enumerated in the GDRP. I say fortunately, because if they were exhaustively enumerated, Facebook would find a loophole, and the whole law would be worthless.
One of the 'valid reasons' for storing personal information, is a clear, freely given, consent from the user. This is the one that all the tracking companies want to get, because they think it allows them to do shady things if they can trick the user into pressing 'OK'. But if the user was tricked or coerced, the consent was not really clear or freely given. Hence the sort of court rulings that the article mentions.
So, if you store a cookie for your domain saying 'tracking_consent=false', this is probably not personally identifiable, so you can just do it. No reason for any banner.
But if you track the 'browser fingerprint' that Troy Hunt is talking about, without consent, you are probably in violation of the GDPR. Even if it's not a cookie. And you had a cookie banner.
Let's not forget the infamous ePrivacy directive, e.g. Recital 66:
"Third parties may wish to store information on the equipment of a user, or gain access to information already stored, for a number of purposes, ranging from the legitimate (such as certain types of cookies) to those involving unwarranted intrusion into the private sphere (such as spyware or viruses). It is therefore of paramount importance that users be provided with clear and comprehensive information when engaging in any activity which could result in such storage or gaining of access. ... Exceptions to the obligation to provide information and offer the right to refuse should
be limited to those situations where the technical storage or access is strictly necessary for the legitimate purpose of enabling the use of a specific service explicitly requested by the subscriber or user."
Of course, the relationship between GDPR and the old ePrivacy directive is rather ambiguous.