In my game, after their 2nd time of spawning they had actually recruited a lot.
I wanted to save about 2 Million before taking my first city, to maintain garrisons...
I've got huge garrisons...
...as I saw them close to Amarna, carrying the garrison of a whole city as prisoners.
So I decided to strike imediately and took Amarna with only 1.5 in cash.
After that I milked about 350 troops out of Nibor's Hood, which I could sign up because of the higher troop capacity
of a king then...
It was a hard fight, because they even had Amazons and Demon Worshippers in numbers
...but I had Eagle Knights...alot of them and my Inquisitors also came in handy...
So I think it's more of a coincidence, whether they are hard to defeat or not. Depends so to say
on those, they defeated before