I have found information from years ago, but I am not confident it is up-to-date.
Stiletto always roams at the lower part of the Thundering Steppes (close to Coldwind Cove griffon station). The area is where the entrance to the Brutal Acts of War is. There are several Skindancer gnolls there and some giants.
You just have to wonder around and wait. Back in the day the spawn time was horrid, people were waiting for hours and hours. Now it is not too bad - 10-15 minutes.
You can get someone with tracking and hunt him down, alternatively, just stay close to the shrine (where the named pops up) and Stiletto will appear.