I think its HIGHLY unlikely that the caps themselves are faulty.

It might be that they are the wrong spec, but thats also quite unlikely (although not impossible, reference designs can often be wrong, and graphics card manufacturers might copy the error)

If adding another cap in paralell to the ones you have works.. then well dont for finding the fault,

I would recomend keeping this cap relatively small 1000uf or so, you dont want to damage the Vreg by increasing the charging current on power on excessivly.

If adding a cap does not help then my first thought would be to make sure that the card is kept cool, especially the voltage regulation.
If the fault occours under load, chances are its temperature related IMO.

Nice post anyway Sikarippa, keep up the good work.