Indeed. In addition to speaking to the two thieves, we should probably make it so that finding the first thief is rather easy. (I think he should be surprisingly close to the town, and his hideout shouldn't be that hard to spot either. o.o' ) The second thief, however, I think we'll need the Red Candle to find, since he's hiding under some brush.
Concerning the need for the lockpicks, well, considering that you get both the hookshot AND the Red Candle in the first dungeon, chances are that you won't be -too- lost (In terms of key discovery and usage.) by then, so you just may be able to discover all these thieves by the time you really start to get confused, if you do, in fact, get confused.
The first thief will give some nice clues as to where the second thief is hiding of course. Really should. It'd be screen 2,1 or 3,1 or something like that. The first thief would be "hiding" out in the trees somewhere just northwest of the town's forest borders, around screen 4,4. Sounds about right, I guess. 4,3 maybe. The Master Thief will be around screen F,7 or E,7, if that helps you visualize it.
Help this cat on his quest for World Domination!