In Orobas Fjords- High Hall, there's a lady that offers a quest-and if you read her mind before she offers the quest, she'll give you double the number of Malachite Gems.

Over all, i didn't use my Malachite Gems that often. i didn't want to waste a rare gem on a second rate piece of equipment just to juice my regeneration. i only ever used the Malachite Gems for the Rank 10 enchantments... like +100 Melee/Magic damage on my weaponry, +10 melee/ranged/magic armor on my gear.
by the end of DKS- ED specifically, i still have about 8... when i was done with FoV, i had almost 20.

anywho, when you get the battle tower, you get runners that will collect herbs/minerals/gems for you. everything except Malachite Gems is still obtainable.