SPCR

I use a Matrox Millennium card. In the past, I removed it's small
noisy fan and used a Thermaltake Schooner heatsink which worked
fine.

I had to do some troubleshooting and needed to temporarily remove
the video card. In the process the Schooner was damaged beyond
repair.

My question is: can the video card's tiny, noisy fan be substituted by
using a larger Nexus fan running at a slower speed, mounted over the
same part of the card where the original fan was, or is there a risk
that it will not cool the video card enough?

Thermaltake Schooner is overkill for that card. You could probably cool it passively with something like a Zalman ZM-NB47J. Or try the stock heatsink with a Nexus fan pointed at it, as you say.

I used Matrox cards in the past, good analog TV out.. Ah, the memories.