Different results obtained for OneVsOneClassifier (or OneVsRestClassifier) when using ordinary KFold and StratifiedKFold cross validation
TL;DR

Use StratifiedKFold and the best performing model (either OneVsOneClassifier or OneVsRestClassifier).

Splitting your training and test set.

Below is are the two approaches you could use for splitting your train and test set. The KFold and the StratifiedKFold:





The main difference between the two is that StratifiedKFold will ensure that the class distributions are always the same in train and test. If you would use simple KFold, it might be possible that a class will appear in the test set, but never in the training set. If that happens, all the samples from that class will get wrongly predicted. So, StratifiedKFold at least gives your model a chance to see one sample from each class.

Regardless of the model you pick, use StratifiedKFold to evaluate your model.

OneVsOne or OneVsRest

It is difficult to say which model would perform best because it will depend on your data's distribution. So, I would say for you to evaluate both and pick the best performing one.

What is interesting, is that you get to choose what best performing means. It could be 
the mean precision/recall/F1 score in a cross-validation setting. But it could also be the one that uses less memory, or the fastest. In general it is a mix of all these things with tradeoffs between them. In general, the OneVsOneClassifier performs better in the F1 score, but it is slower than the OneVsRestClassifier, but please not the words "in general". Perform your own tests and see which one works for you.

I usually prefer the OneVsOneClassifier, because it tries to model every class against each class. This way, classes are self contained and finding boundaries around that space is more convenient. When you have a OneVsRestClassifier, you need to model the "rest" class, which can be really complex since it is made up of various classes, which can become problematic.