Continuing on my Fire Red run from before, I'm level grinding on Route 19 and send my Fearow to battle a Shellder. I'm running low on PP for Drill Peck, so I opt to use Fly. Turn 1, he reveals Protect as I Fly. Okay, not that terrible. Alas, Fly misses, but he uses Supersonic, which also misses (55% accuracy, hell yeah). Turn 3, I Fly again, he uses Icicle Spear, which obviously misses. You would think he would Protect on turn 4, but instead, he uses... actually, I don't know, because Fly OHKOed.
tl;dr AI handles 2 turn moves a little funky sometimes.