If neither one is holding an Everstone, then its selecting the natures with a RNG (Random Number Generator). Its entirely random, so other than the Everstone, you've just been unlucky so far and need to keep trying. Good luck in your endeavors!
Its just rng [not sure what that means but..]