Looking for the right word to describe a type of soldier

Personally, I'd go with Sniffers, Seekers, Trackers or Hunters, maybe even Hounds since their job is to track down and kill.
Like someone pointed out, if magic is illegal and mercenaries are the ones that take care of them, then there's probably more than one way to do it (Assassins who track down specific targets, hunters who track down any magic users, thugs who kill any magic user they stumble upon, etc)

 

I know the author said he didn't want to make up a term to describe these men, but it seems like the best solution since none of the offered names seem to fit. This reminds me of the assassins that were sent after the Confessors in Terry Goodkind's The Sword of Truth series. The men were all sent in groups of four with the express intent of killing a chosen confessor. He called them quads, which makes sense. Maybe nomenclature based on the nature of the hunters would be wise.

 

Magehounds is a great suggestion. Sounds threatening.

 

I'm assuming they are part of an order but what if you do something with their sigil?
Example: Order of the Flaming Rose. Your 'catcher' could be called a 'Scarlet' for instance?

 

Inquisitors. These catchers sound like they employ some very nasty and forceful tactics. They bring to mind the Spanish Inquisition (no Monty Python please haha!) being that they hunt down and stamp out anyone who uses magic and how this parallels with the SI's role in the church.

 

I mean you could actually take stuff from games and things like this two that come to mind would be Anti-Mage from Dota/Dota 2. Of course these are games but that's immediately what comes to mind when I think of someone who hunts down mages and kills them. If you don't know some of the lore behind it's pretty interesting.

Could even go with something like Magebane (Hero from HON) which fits the name of what your looking for very decently. When it comes to writing sometimes simplicity is often better then coming up with your own words.