First step I recommend is ensuring you've CB AntiSpam installed and its captcha configured. This will catch most if not all automated bots. You're then left with human bots who register then had off the account to an automated process. Typically the automated bots will try to spam forums, which you can use the below usage in CB Auto Actions to try and protect against.

www.joomlapolis.com/documentation/291-cb-auto-actions/tutorials/18810-blocking-kunena-forum-spammers

As for your issue no substitutions are not supported in the searching. Joomla search is even less powerful than ours so it won't work there either. You could maybe create a frontend userlist though and have an Advanced Filter which directly adds to the database query to try and match your spam criteria to at least help find them better.

If there's a common element to their email address though you could use the auto blocking feature in CB AntiSpam to try and block similar email addresses from even being allowed to registered, but a lot of the time they'll use a compromised email account to register.