Its very weird but here is how it works:
1. All trainers turn around once in a while, so sneak up from exactly behind, where their Pokemon faces dosen't count
2. trainers spot you from behind (like 2 furfrou long) it will be very high, unless crouching - if running you are toast
3. if your Pokemon is slow that means it is slower to move towards the target, giving them more time to spot you
4. (the most confusing) if you are running behind them, they will turn around (yellow) and spot you (red!)
so in conclusion: crouch exactly behind for maximum evasion, running is a death sentence :)