Encrusted....hmmm, my memory sucks....enchanted are Hulking Stone Eles....icy are Ice Golems....you may have it right but I didn't explore the desert too much.
I think Enchanted Lodestones were renamed to Scorched Lodestones in Post-Searing, but I'm not too sure of it. But yes, Encrusted Lodestones are definitely from Sand Elementals found in the desert and Dragon's Lair.
