To ban or not to ban...

[tempest]

I'd much rather them be banned, as if they use the cheats in a private server, they might/will use them in a public server.

You can't just assume that. Maybe they're more likely to cheat on pubs, but you don't have proof.

Cheating on a server connected to the master server is cheating no matter what.

So "cheating" on a server that's listed on the master, but private/password-protected, is so much worse than cheating on an open, but non-listed server. Now which one is easier to get into by accident?

I'm absolutely certain they're using the same clients in public games, and they are almost certainly still cheating (to a much lesser extent), but the public demos I have are nowhere near what the community at large would call proof

That remains to be seen. You should really show those demos - if there's even the slightest indication of them cheating on public servers, I guess everyone will be with you.