Like the pp I interviewed 3 nannies, hired the one we liked best and she's been with us for almost 3 years (and hopefully will be with us another 2 or 3 years until the kids are well into elementary school.)
I hear so many horror stories that I feel very lucky we found someone great. But we've also been extremely flexible with her, and with what we require vs. what we allow her to determine/do in her own way. I think that if we were more rigid in our thinking or requirements we would have had more turnover.