You start in the Outskirt Sands. You'll get an e-mail. Head to the Under and talk to Nett. Go to Pyrite Town and talk to a kid behind the bookcase. It says that Cail fought a Pokémon Trainer with a Shadow Pokémon. Talk to Cail who will battle you. If you didn't snag his Furret he'll have it. After you battle him, he says it's in the Snagem Hideout, which is now on the map. Head there.
Up to six Pokémon Trainers with Shadow Pokémon that you failed to capture will appear. They won't let you by until you've snagged all their Pokémon. This includes Skrub with Hitmontop and many other minor Peons.
Why are you here? You're looking for one of the other Shadow Pokémon starters.
All Trainers here don't have Shadow Pokémon and are optional. Search the base until you find him. He's below a Snag Machine.
Snag the starter he has and leave the base. Next up is the last one.
Finding Johto Starter 3
You'll get an e-mail from Nett, so go to The Under and talk to him. Nett will tell you that a guy named Gurks has more information about shadow Pokémon. Gurks is located on the second floor of the junk shop, on the outside balcony. Gurks tells you he battled a colored peon in The Under, but don't bother looking for him there. Instead just go to the Shadow Pokemon Lab. You'll get an e-mail telling you that the colored peon is inside.
This one is simple. The third Johto starter is where Ein was. Just look through the Shadow Pokémon Lab part of the walkthrough. It's the same guy essentially, just a different Shadow Pokémon.
You get a D-Disk for beating him. If you enter it into the UFO in The Under, you can go down. This will take you to Deep Colosseum, where 20 opponents are: 15 miscellaneous, 4 Cipher Admins, and the fabled Deep King.
Simply head back to where they were in Realgam Tower. You can reface all six Trainers atop it as well, including Nascour and Evice. You can't rematch the three Cipher Peons who had Shadow Pokémon in the first part of the Tower with the rails.
The Final Shadow Pokémon
Once you have seemingly every Pokémon you'll start getting tons of e-mails. It'll lead you to the Outskirt Sands, where one last Trainer is...