To steal a little from football terminology:
Within reasonable limits, speed should not effect the AC of a creature. A creature with a fly speed of 250 that is using a run move (flying as fast as possible) moves at 113.6 miles per hour. That is pretty much the high speed limit in 3.5 rules. That is about 20% faster than a major league fastball and a significant amount slower than a jai-alai ball moves (if you don't know what jai-alai is, look it up ... a cool sport ... sort of like 'Track Ball' against a wall on steroids.)
If a major league batter knows exactly where a fastball will be thrown, he'll smack it almost every time. It is only when he doesn't know where the ball will be (due to the possibility of there being spin on the ball, etc ...) that he has trouble hitting the ball.
In jai-alai, the pelota/ball has been clocked at speeds of 185 miles per hour. There is a more consistent spin on the ball when it if flung from the cesta, so it is easier to predict where it will go. If a player can get near the ball, they'll usually catch it in their cesta.
Of course, speed does make it a bit more difficult to connect with a target. I'm just saying speed by itself doesn't make it that much more difficult.
Quickness, on the other hand, makes it harder to connect with a blow. Dexterity covers quickness. Quickness would be the ability to make sudden changes in location that make the attacker aim at a spot where the target will not be.
With the exception of dragons, most creatures with great speed also have a great dexterity. In those situations, I'd say the issue is well covered. If you feel that it is not covered, you might consider giving a +1 or +2 circumstance bonus to AC for moving very fast.