The Cactuar desert is south of Maranda, by the way. Due to their high Evade and defence, it's best to use attacks that ignore defence and can't be blocked. If memory serves, equipping the Offering is one way to kill them. Blitz, Bushido/SwordTech, Tools, and Ultima also work, I think, and I'm pretty sure the Atma/Ultima Weapon also works.