The intonation adjustment is compensating for the stiffness of the string. In an ideal world, the string vibrates purely and perfectly, but real strings aren't like that at all. The E string is fatter and stiffer than the G string, so the bridge adjustment will be set to compensate for that stiffness by making the string longer.
When you are hitting harmonics or fretted notes at the high extremes of the neck, the string stiffness is conspiring to throw off the tuning. The intonation check that you did at the 12th fret is an approximation for all the different lengths of notes on that string and the approximation isn't good anymore for that string in the high ranges.
One way to test this is to try a different set of strings - something radically different (gauge, material, or manufacturer) will probably exhibit different intonation behavior, and you may luck into to finding something that works better (of course, the E and A may NOT work as well). Different brands may have the same final gauge, but have a different mix of the size of core and wrap wires which will affect the stiffness a lot, as you've noticed when resetting your intonation when you try out a new set of strings. This isn't a matter of string wear or "badness", it's just the characteristic of how that particular string was made.
The intonation adjustment is an approximation across the entire neck. If you play really high, you can set the intonation at a higher position on the neck to make the high notes line up better. And you don't have to have a dead on match either - if you set your intonation at the 12th fret either +/- 10 cents (I'm not sure which way is "crescent", either) and the intonation is better by 10 cents at the 24th fret this may be a good compromise. When you see alternate intonation setups like Buzz Feiten, they are intentionally setting a different relation between fretted note and harmonic to try to correct the approximation for the real chords that people play.
With regard to whether there's a neck issue - if the fretted notes are in tune, then the frets are in the right place and there's not an issue. The height of your action will definitely affect the fretted note tuning, so you may want to reduce relief if that's still playable for you and you really hear the tuning issues.