I always do a list of ten names for each culture in the game. Cross them off as used, and replenish between sessions. Also I try to make sure each name starts with a different letter.