I think Fake Out trainers are programmed to use Fake Out as the first move unless it's a Ghost Type, or am I horribly wrong about this?
I think they are programmed to do that. In White, I led against Cheren (this is post-game) with my Tyranitar. His Liepard used Fake Out turn 1. Liepard's Fake Out was weaker than the sandstorm that Tyranitar summoned, but Cheren kept doing that.