Then you head to Pal Park (located on Route 221 in D/P/Pt, and Fuchsia City in HG/SS) where you can participate in a catching game to try and catch all 6 Pokemon, using Park Balls that are given to you. They have a 100% catch rate (similar to the Master Ball) so you'll catch the Pokemon without fail.
It's only on the DS and DS Lite though, so if you're using a DSi or 3DS you cannot utilize this feature.
More information on Pal Park can be found here. Good luck with completing your Pokedex!
Is this also the case in Gen III then? The Legendary/Unobtainable Pokémon aren't necessary for completing the Pokédex such as Lugia and Ho-Oh.
Things would be so much easier if we could trade with Gen II games... ¬.¬