I've used those tie-ribs (small metal wires covered in plastic) before to mount fans on stock heatsinks of AGP Geforce 6 cards before, though those cards have much larger heatsinks. It's worked perfectly for as long as I used that computer regularly.
I'm not a fan of using glue though others on Vogons have found that to be a good solution. I don't like it since it's sorta permanent 😜
One thing you could try is to mount a (small) CPU HS cooling fan on the Voodoo's HS using screws (though that leaves traces and scratches on the Voodoo's heatsink) though I've personally never done that on a Voodoo.
Some AT cases have the option of putting a fan behind the front bezel so it gives 'some' cooling to the expansion cards, though I'll assume yours doesn't have that option.
Btw, those Voodoo 3's always tend to get quite hot so that's not that abnormal.
Whats the rest of your system btw?