*sigh* Quests needing "X number of Troop Y".
 

So what to do when you can't get any of the troops he needs? Just lose out on the quest? I need "Robbers" but there arn't any for example. Maybe they'll show up later in the game when the gold and xp from the quest is worthless?

There are no robbers anywhere? That's strange. Have you looked on all of the first four islands (at least)?

Yeah, nothing on the first 4 so far. I peeked into Verona but I didn't find any at the areas I could get to.

I've found units that have the "robbers" attribute, but when I took them with me, the NPC didn't accept them. So I'm looking for a unit actually named "Robbers". I assume there is one? If not then no idea, I'll check the quest again, make sure I didn't miss something.

There is. You should also be aware that you have to go to Sohaty with all the units he requires - this is one of the downsides of that quest - giving units one by one doesn't work.

Robbers are almost always guaranteed on debir, in the cave. Curvy Eyes usually sells some, so you can check him out before killing him. The building next to his hideout usually has them, but it's completely normal to get a sucky randomization and be left without Robbers in these places.

Dont count on robbers in late game, if they are nt on debir,scarlet,bolo rusty or verona there is almost no chance they will aprear later ... in my last game the only place i had them was robbers cave

Just this minute found some. Barbarian Tent on Verona. Took a lot of searching though :p I was surprised I hadn't seen them much earlier though, they're a basic unit after all.