Of course, the Bitcoin blockchain and any transaction moving coins is public (on-chain). The interesting question is indeed, how deep do the "common" exchanges actually track coins?

I would assume they don't do it themselves, but use one of the questionable blockchain analysis/tracker services, that spit out some sort of intransparent risk score for an address. It's unlikely those services let the public look into their inner workings and so it remains a mystery how deep back in transaction history they look and by what means they taint coins.

This intransparency sucks.