If I were to use a normal-type Pokemon that could learn Recycle, and gave it a Normal Gem that would boost the power of Fake Out, then could I re-use that normal gem for another move, like Strength or something?
Recycle allows the user to regain a held item, such as a Berry, once it has been consumed. Consumed items are not forgotten when the Pokémon is switched out. Recycle cannot restore items that were transferred to another Pokémon (such as via Thief) or items that were knocked off.
Yes, Recycle should give your Pokemon the Normal Gem back, as it is an item that can only be used once.
Source
