On servers we host, how can we block people that are using CheatUtils?

You need different anti cheat server plugins to stop working particular modules. But there is no simple way no block all users with specific mod. This is how all minecraft mods work.

A mod can offer a way to block that. E.g. ReplayMod offers a plugin on https://github.com/ReplayMod/replay-restrictions that will send a serverpacket to stop recordings from working.

I don't approve cheating on the servers where cheats are not allowed, but sorry, I will not add this. Replay mod is very popular mod, and CheatUtils is maximum at few hundreds users.
Moreover, I have more popular mod FreeCam, and someone could come with the same request.