The NV section of the CogAT is the part of that test that should have picked up the VS stuff. I say "should have" b/c it is not at all uncommon for gifted kids to do more poorly on multiple choice group tests. At his age, time and reading skills won't have come into play b/c it is only read to oneself and timed starting in 3rd grade, but that can be another issue with the CogAT for gifted kids.
I have one child with high-ish scores on the CogAT (certainly above avg, but not GT) who has individual IQ scores that are above the 99th percentile. The interesting thing is that her strengths and weaknesses are totally different on the CogAT vs. WISC (IQ) as well.
The counselor dd has seen for other issues, like me, is not a huge fan of the CogAT or other group tests and reminded me that they are not intelligence tests. Interestingly enough, I also know a very few kids with scores on the CogAT that qualified them for a GT id locally who were later tested on IQ and weren't much above average. Of course, our local programs are pretty liberal as to what would qualify for GT with the CogAT (95th percentile in any one area).
I'm surprised that they would rule him out based upon one score not qualifying when the other two (MAPS and NNAT) so clearly do. I might start with contacting the district GT coordinator to discuss how they id gifted. Do kids need to qualify on everything with any one bad day/low score ruling them out? I'd think that it would be a pretty small program if so! Especially given that scores on achievement and group ability tests tend to fluctuate quite a bit in elementary students (see:
http://faculty.education.uiowa.edu/dlohman/pdf/Gifted_Today.pdf), I'd be really leery of that type of system. See if they'd take individual IQ scores.
Given what else you've said (teaching himself to read at four, current achievement level, NNAT scores), I'd bet that he'd come out gifted on an IQ test. FWIW, his CogAT scores are about one standard deviation above the mean (approx 86th percentile), so not just slighly above average.