There are several things here to help patch up the holes in the plot.
Firstly, in-game, the name "Horadric Staff" makes it appear as though there is only one. There was more than one Horadric Mage, and therefore, more than one Horardic Staff (emphasis mine):
To safeguard Tal Rasha and prevent anyone from freeing Baal, the Horadrim sealed Tal Rasha within an ancient Tomb. The only key to unlock Tal Rasha's Chamber would require the possession of Horadric Staves, which they guarded fiercely. In order to further confuse any would be adventurer, the Horadrim placed the tomb amongst six False Tombs.
Source
This next part is unfortunately less clear, but the wiki can again give us some insight. Basically, (if we use the assumption that they did enter by way of the Staff), Marius was tricked into releasing Baal, and now there were two Prime Evils (although somewhat weakened) wandering through Sanctuary. They did have the strength to fend off and Seal Tyrael in the tomb, once Baal was freed, as well as summon Duriel in order to fend off the heroes that were chasing down the Dark Wanderer
Finding the tomb, the Wanderer appeared to gain strength. Or rather, as Marius observed, appeared to be losing what was left of his humanity, his visage becoming more demonic. Either way, the Wanderer led the way into the tomb, undeterred by the gloom. Eventually, the pair reached the Binding Stone where Tal Rasha, barely containing Baal, stood. The Wanderer moved forward to release the Lord of Destruction but it was here that the archangel Tyrael intervened. The Wanderer and angel did battle but Marius, manipulated by Baal, released him. Marius promptly fled with Baal's soulstone, but it mattered not. Baal was free. Tyrael was imprisoned in his place. And with that, the Wanderer and Baal set sail to Kurast.
Source
Diablo freed Baal from his imprisonment in the Tomb of Tal Rasha. As punishment for his part in the Dark Exile, Baal left Duriel behind to guard the tomb. Embittered by this new position of solitary servitude, the Lord of Pain claimed the souls and blood of many bold adventurers. Finally, Duriel met his match in a group of heroes who were pursuing Diablo.
Source
So, given the ability to summon a Lesser Evil to Sanctuary simply because he held a grudge, could hand-wave away a little bit of masonry work.
Additionally, the order of which the three Prime Evils were caught and sealed (Mephisto, Baal, Diablo) could also support Diablo's knowledge of Tal Rasha's Tomb, as well as a potential alternate way to find and enter the tomb, without needing the Staff.
The first of the Prime Evils to be captured was Mephisto. […] A binding stone with runes of containment was built, and Tal Rasha ordered his brethren to chain him to it. As the mages looked on in sorrow, Tyrael jammed [Baal's] soulstone shard into Tal Rasha's heart, sealing his fate. Sorrowfully, the Horadrim sealed the chamber and departed. […] With Tal Rasha's sacrifice, Jered Cain became leader of the Horadrim. He and his surviving brethren began their search for Diablo, following the trail of terror the demon lord left for nearly a decade. Their hunt took them into the western lands of Khanduras where Diablo, along with a demonic army, was finally confronted and imprisoned within his soulstone.
Again, there is no real hard links between all of this evidence. Hopefully it's enough to connect the dots.
