Keeping a list of "fingerprints" of users is hardly invasive, and it's only dangerous without proper database security.
It can throw up false positives, but the key there is to make it as good at not doing that as possible, and having a reasonable means for users who feel like they were unfairly tagged as evaders to appeal the flag.
Also, don't do it automatically, use it as a tool to identify possible cases and have a review team check for which ones need the most immediate action, with help from a separate algorithm that prioritizes user reports by how reliably a users' reports have pinged actionable content.
That's the entire game of security, not being perfect, but being good enough for the adversary to decide you might as well be perfect for all their efforts would be worth, and ban evasion protection and bot prevention are no different.