It's also worth noting that, originally, the Courier's Stash load outs were not given to every player. Rather, specific games retailers who you pre-ordered from, each had a different one of the four load outs. The only company I remember that participated was GameStop, don't remember which outfit came with their version of the pre-order. But you get the idea, a retailer specific pre-order bonus, where it would only be possible to get one of the four.
Then after the game and most of the DLC had shipped, the four outfits were packaged together as a a horse armor tier cash grab.
The important thing to take away here is that, from a canon perspective, I don't think we should assume that any courier actually has more than one of these outfits. There's a version of the Courier with the Vault 13 get up, a tribal Courier, a veteran caravaneer Courier, and a mercenary Courier, each of these help you to role play. But I don't think that there was any courier carrying all of these get ups around with him.
As to your question of how the Courier would ever get their hands on Vault 13 gear - hard to say, but at the same time there's any number of possibilities. Maybe your Courier is actually a descendant of the Chosen One (I have a feeling this is what they were going for at least as a possibility, given that the last West Coast game had you as a direct descendant of the first game's protagonist). Maybe your Courier ran into an antiquities dealer that was selling Vault 13 gear unrelated to the Chosen One or the Vault Dweller (there would have been a lot of gear in Vault 13, and it doubtless would have been valuable to those who found it after the Deathclaws were massacred).