I have been having this problem in spades.
I have rendered frames of an animation overnight at least 10 times, each time changeing various parameters and somtimes they occured and somtimes not.
I have a quad core Q6600 and when I finally set the max threads to 3 there were no more missed triangles and I rendered a 2000 frame animation without a single occurance. I switched back to 4 threads and the triangles were back. Went back to 3 and no black triangles.
I think quality and frame size may have an influence although I changed so many settings I lost track. I finally concentrated on the render settings as they seemed to have more influence on this bug but I have nothing certain there except the number of threads. Could it be somthing to do with the multi threading loosing track of which thread has rendered which triangle, where each thread thinks the other thread has rendered it and in fact none of them has.