Você está quase lá, o *
não está fazendo o que você acha que corresponde a 0 ou mais do caractere anterior tente
^<HOST> -.*(AhrefsBot)
por exemplo
fail2ban-regex '5.10.83.65 - - [18/Mar/2014:09:06:38 +0400] "GET /catalog/product_compare/,,/form_key/QLZ6ZkIwX3FWqme3/ HTTP/1.1" 302 522 "-" "Mozilla/5.0 (compatible; AhrefsBot/5.0; +http://ahrefs.com/robot/)"' '^<HOST> -.*(AhrefsBot)'
Running tests
=============
Use failregex line : ^<HOST> -.*(AhrefsBot)
Use single line : 5.10.83.65 - - [18/Mar/2014:09:06:38 +0400] "GET /...
Results
=======
Failregex: 1 total
|- #) [# of hits] regular expression
| 1) [1] ^<HOST> -.*(AhrefsBot)
'-
Ignoreregex: 0 total
Date template hits:
|- [# of hits] date format
| [1] Day/MONTH/Year:Hour:Minute:Second
'-
Lines: 1 lines, 0 ignored, 1 matched, 0 missed