I finished listening to Tribes of Tokyo, and went back to the relevant episodes of Sense of the Sleight of Hand Man. Lucille's timeline is surprisingly complex. Mitchum pulls the Thompson out of a trash can in NYC, but he definitely doesn't plant it before getting picked up - he makes a point of saying he has it with him when he goes to the restaurant. I'm guessing the Tongs were fine with it because they knew that if he tried to start something, getting the Thompson out of a case would take too long; they could just shoot him while he was undoing the clasps. As far as I can tell, this is what happened.
First, Mitchum Cleary time travels back to the twenties and winds up in New York. He goes to his appointment with Mr. Lao carrying Lucille in her violin case. He leaves her along with his body in the Peach Blossom restaurant when he enters the Dreamlands.
The first thing he does when arriving on the Plateau of Leng is to look for Lucille. Unable to find her, he arms himself with a rusted old sword he finds.
While in the Underworld, Mitchum dreams up Lucille as a magic weapon. This version of Lucille is presumably left behind either in the Enchanted Woods or on the Steps of Deeper Slumber when he heads back to 1920s New York.
Mitchum is then drawn supernaturally to an old trash can, where he finds a rusted old Thompson wrapped in dirty newspapers. He calls it Lucille. It's not clear where this incarnation comes from – I'm getting to that. However, Mitchum eventually carries her to Chicago, then to Bryson Springs, to his fateful encounter with a Yithian, and then back to the Peach Blossom.
Some time around 2012, Lucille winds up in the hands of John McCaffee, who gives it to Ito, the yakuza member of the Ronin/Empty Five. David mentions Ito having a Thompson during the final assault on the temple, and the only change to his equipment that Ito makes before going through the toru gate is changing his suit. This means that, in 2012, Lucille finally makes it to the plateau of Leng where Mitchum looked for her almost 90 years earlier. During the fight with the Guardian, Ito ignores Lucille and chooses to use his family's ancestral katana instead. Lucille is left behind yet again when Ito goes to sleep and returns to the corrected timeline.
Lucille never gets rejuvenated like Mitchum does, so it can't be stuck in a time-loop, since it would become infinitely old and fall apart (and also never reach Ito). The most obvious way for Lucille to get out of the loop is for Mr. Lao to sell Lucille or give it to one of his men, starting it on the journey to McCaffee; the gun left in the restaurant doesn't get left in the trash can (although it was left there earlier). In Lucille's subjective timeline, it first encounters Mitchum when he pulls it from the old trash can in New York, and leaves his hands slightly earlier after going through Bryson Springs and the Yithian. Where does Lucille come from before then? Presumably, it was either being discarded after being used in a crime (since 20s ballistics might not be great, but there was really only one kind of person who used a Tommy gun), or left as a dead-drop for someone else to pick up. Alternatively, it might have been some emanation of the magic Lucille into the Waking World. If that's the case, then its final arrival on Leng really brings it full circle. In the un-reset timeline where Nyarlathotep talks to the Ronin, Lucille would probably be picked up by the North Korean ghouls, who might one day return it to their friends in the Underworld. In the reset timeline, it remains in the hands of McCaffee, and in the Delta Green timeline, who knows?
There's a certain irony in the way that Ito went out of his way to bring a sword with him to Leng when he had Lucille, while Mitchum found a sword as soon as he got to Leng but went through a whole lot of trouble to find Lucille.
