I think you can face Malboros in Grandidi Forest (the forests around the Chocobo Sanctuary), and you can sometimes win Curse Spikes from them, though they're pretty dangerous. You can also Card Mod Tri-Face cards into them (1 card for each Curse Spike), & you can get those pretty much anytime throughout the game.
I don't think they appear outside Dollet, though I might be wrong. If the OP is willing to advance the plot a while before collecting them, though, s/he can encounter them in (mild spoilers) the Galbadia Garden lobby.
Minor spoilers:- - - - - On disc 2 the ONLY tri faces are via the Balamb Gardens MD level area or right next to Cereburus GF via Galbadia Garden (end of disc 2).
Else you will have to wait for the fixed Tri Face battles on the way down to Ultima Weapon if you don't want them from Malboro's.
Besides if the only reason the TC wants the cursed spikes in the first place is to convert them into 1 Dark Matter the fixed ones are the only ones worth fighting since Siren must be at max level to convert them and odds are the TC won't have any GF at max level until after getting the Ragnarok.
There's away to avoid fixed battles down there and you can still encounter them in random battles.
There is, but if you want Curse Spikes, why in the world would you avoid them? And yes, you can, but there's no real benefit to encountering them on the ICTHeaven - you can't access that any earlier, and the fixed encounters are far more useful (especially if you want more than one Dark Matter).
what I meant is Tri-Face is STILL a random battle in the deep sea ruins even if you didn't trigger the fixed battles. Still, I agree, having the fixed battles may be a more efficient way of farming Curse Spikes.