If you're starting over, you might as well rng your TID since it would also allow you to know your SID, and hence what other frames are shiny with your ID's. So...
1) RNG your ID's. I found this guide to be helpful (
http://www.smogon.com/ingame/rng/rs_nonbredrng). Note that as I indicated toward the middle of page 1585 of this thread (I could just quote it, but I think the context is also important), the frame before the one with your ID's (according to the guide) will be shiny.
a) So if you follow the guide, and you find the frame you got your TID on, use the frame before that one to deduce your TID and your SID. The first 4 digits (in hex) of the PID will be your TID, and the last 4 will be your SID.
b) Once you know your ID's, plug the correct ones into the reporter and regenerate the
frames. If you click the "shiny only" box, you'll see all the frames that are now shiny. Leave the method as Method 1. All of these frames can be used for the legendaries.
c) So to rng a legendary, aim for the time associated with one of those frames, and see where you land. Subtract the delta from the time of the frame you are aiming for, and just keep trying till you get it :)
2) This is optional, but it you can also verify that you hit the ID frame that you were after but trying to rng a shiny starter. It's easiest to do so imo if you try to hit your ID seed again, that way you already know where to look, and so that you can find the PID of the shiny, and thereby your TID and SID. Just an extra step, but who doesn't like shiny starters?
So you'll need a timer. I use the PikaTimer, but the EonTimer can be used just as well (if not better) I think. All of this is for Sapphire, as I have never played Emerald. Since the frame with your ID's will be shiny, it's best to aim for a frame with good IV's/nature when you rng your ID's so that you can ensure that at least 1 frame will be really good and shiny.
All I have used the Pandora's box for is when I rng'd my ID's in gen V. It looks like it can also be used for finding what frame you hit for your ID's in Gen III too, so you could try to use it as well. Basically, for the later gen's it allows you to know what ID's you have to aim for in order to make a certain frame shiny, or to quickly find what seed you have to hit in order to get ID's that you want. Again, I've never used it for gen III, but it appears to also find the frame you got your id's on, saving you some time. Not really sure how it works though :P