I came across a rather troubling thing my nuzlocke. See, I have a combusken that can end the average Pokemon in one or two hits in the sandstorm area where there are higher level Pokemon. the higher level pokes means better exp. However, When I use Double kick or any move with 100 accuracy in the sandstorm, it sometimes misses. I've checked bulbapedia and found nothing on the sort. I'm playing a gen 3 game.
Some Pokemon have sand veil as an ability that raises evasion in sand.