Are the ore veins regenerating? Because I think I've been to most of them and if they don't get new ores in them it'll hurt my chances of getting this rare gem.
Also do you know somebody who sells them or maybe a sidequest? If so, where?
No, ore veins don't regenerate. There's a limited quantity of Malachite Gems in the game, and if you use them all, you're out of luck forever.
Read my ED guide, and it has a list of all gems in the game (ED, at least). It should still apply to DKS, I think.
