I believe that using the "Clear and re-build all training data" for face detection makes the detection worse with the more faces you have tagged.

Initially I manually tagged 4-5 faces of a few people and detected faces (I have around 10000). The initial scan went well and I'd say it was 80% accurate.
As I tagged more people manually and rebuilt the training data the new Recognise Faces runs got worse.
I now have 2000+ faces tagged over 50+ people and the accuracy is almost 0.

I believe that it now has too much training data and the faces are too different across all the images to train a model properly. I'm not sure how other engines cope with this problem. (e.g. I am now tagged over 1000 times in my albums).

What might be a simple workaround is to allow a user to choose 4-5 good images for each person and use those as the training set rather than trying to use every example.