Well, if you unlocked the extra ending at the end of Devil May Cry 3, you'll notice that Vergil dropped Yamato's sheath while in the underworld, about to fight Mundus.
So it's entirely possible that, in the search for Yamato, Dante went to the last place that Vergil stood uncorrupted by Mundus and found the sheath of the blade.
Of course, this is only speculation, but given the fact that Dante was searching for the blade in the first place, I think that this seems likely.