I had a lot of the feelings that you describe when my son was three. I also took the "Ruf" test. It helped by indicating that he was advanced - but the levels are a bit strange and inaccurate (at least for us).
DS6 goes to a private school- so far, so good - until first grade. He's bored with the work and starting to make careless errors on homework and quizzes, which further confuses the issue with his teachers.
If you decide to go private, Montessori might be a good option for a gifted kid in the early years- less stifling than early elementary classrooms.
