Johto: National Park (Come 1st in Bug Catching Contest), Route 42 (PokéGear Phonecall) Kanto: Route 25 (Show Bill's Grandfather a Marill in HG or a Staryu in SS), Seafoam Islands Shop: Johto: Pokeathlon Dome
Source: Serebii.net, http://www.serebii.net/heartgoldsoulsilver/items.shtml