Before leaving Shadow Square, buy a magical banana at Notaku's, in Caravan Way. If you forget it, Marcus in Altaruk might have some...

Then, go to the Defilers' Desert, the sandy area just West from Altaruk. The stupid little halfling can be found there... First identify yourself with a meaningless chat where the words "not too" appears, then he will ask for the banana. Try not to disintegrate him, give the banana and hear what he says, then head back to VA headquarters to report.