Faced with the need to locate strange things in a strange city, Borgrim grabs someone scholarly looking, frowns at him like violence is not to be ruled out, and asks:
Scholarly person! Tell me immediately where to find black pearls and/or lotus blossoms in this town! It's of vital importance.
So ... every test is really an Intimidate test =D
And I restate my suggestion that Intimidate be Strength based =)