Missingno. Master
Poison-type Trainer
Incidenatally in Platinum, I found you don't even need to be near the rocks (Moss and Icy) in order for Eevee to evolve.
I had just entered Eterna Forest, and my Eevee levelled up, and it tried to evolve. I almost missed that, and I would have ended up with a Modest Leafeon nicknamed Auroreon. haha Same with the Icy Rock on whatever route it's found on.
It's like that in diamond and pearl, too. Your exact location compared to the rock doesn't matter. Eevee will evolve into Leafeon when leveled up anywhere in the Eterna Forest (though not in the Old Chateau, nor in that narrow path outside the forest that requires Cut). And into Glaceon anywhere on Route 217.
As for HGSS handling these evolutions;
Leafeon: Leaf Stone. It's what they should've done in the first place, and don't give me any of that "it could've been done before" crap, the same can be said for Lickitung and Piloswine's evolutionary methods.
Glaceon: New key item, Icy Stone, which works in the same vein as the Gracidea, except it works all times of the day and evolves Eevee to Glaceon. Will become a regular item in Generation V, I'm sure.
Magnezone/Probopass: See Glaceon, except replace Icy Stone with Magnet Stone, Eevee with Magneton/Nosepass, and Glaceon with Magnezone/Probopass.
Also, I predict that in future generations, Espeon and Umbreon will be evolveable via Sun and Moon stones, respectively LIKE THEY SHOULD HAVE BEEN IN THE FREAKING FIRST PLACE!