I would personally opt for a mixture of the latter two, or possibly all three. Perhaps there is a way through exploring or after battle to recruit an enemy, but you're more or less locked out of it at the start. Rather than needing a specific item, you need specific information about the enemy in order to build a persuasive argument towards them joining you. This information might be gathered by contextual clues while facing the enemy in battle or observing them out of battle, could be gained by asking them directly, or perhaps you could go back to town and ask around on what that sort of enemy likes, which would also lead to the possibility of more NPC interactions even if these would be primarily dialogue. Having information rather than specific items or specific exploration scenes would mean after you've recruited an enemy once, you can do it again without having to repeat a large portion of the overall process.
The biggest downside to this approach is that it would be a lot more complicated to implement. You'd need to code in checks for specific interactions or have a list of stages to weigh the checks against. It could also result in branching dialogue or interaction paths so players would still need to build their argument through a few branching dialogue/interaction options rather than automatically recruiting an enemy.