The CEO has decided that you have technical ability but not management ability. He doesn't want to lose your nagios-installation skills but he thinks that an imaginary person whom he has not yet met or hired will be better than you at leading the tech team. He's happy to let you keep the fancy CTO title and perks so you don't lose face, or because he doesn't want a confrontation.
I would guess based on your comments and the fact that you're asking this question that politics are not your strong suit. "Politics", b.t.w., is just the natural state of people working together... it can be dysfunctional or functional, but as soon as you have 3 people, you have some kind of politics.
Since politics are a major component of management, you may actually be happier not doing management.
In situations like this the CEO is probably overestimating his ability to find a Magical VP Technology that will magically solve all his problems (unless he has someone in mind, a buddy from a previous company, for example). Likely he will spend 6-9 months trying to find someone, finally hire someone imperfect in despair, and spend the next year or two discovering that person is incompetent, too. But now I'm really just projecting.
If you don't like the CEO it may be time to move on. Life is to short to work with people you don't enjoy spending time with.
I definitely read the same thing as spolsky, based on your language that you're not nailing the managing up and out parts of the VPE role, which is why the CEO is looking for someone else.
I know a lot of people project negative intentions onto the CEO in this situation, but it's his job to make a call about what's needed here and it seems like his call is that you aren't up to snuff. At the VPE level, it's not enough to be technically right, you need to be able to turn the engineering group into a cog that runs with the other cogs that the CEO is putting in place.
When I was in this position our board introduced me to some potential mentors with more VPE experience. They all had one identical piece of advice: measure everything and then use that to control the dialogue about engineering with the board and the other managers.
That advice seemed overly political to me (especially the bit about controlling the dialogue). I've come to two realizations about it.
One, a lot of the people who judge you have extremely strong personalities and if you aren't presenting an equally strong opinion, then you won't be able to have a conversation as equals. Facts are what give you backbone.
Two, when you put down an engineering process, half the value is in making your team more efficient, and the other half is in presenting a predictable interface to the rest of the company so that they can get their jobs done. That outward part of your responsibility was the key realization as these people took on more responsibility.
I don't think all is lost for you. Some people would probably project onto the CEO that he has a personal dislike for you, but all you can really infer is that he wants a different type of leader in the VPE position. You would show that type of leadership if you went to him, explained the problems/risks of finding an experienced VPE, and then laid out your plan for becoming that person including asking for a mentor and a proposal for an engineering process that gave him more insight into the company.
Now you might not want this role or might not have the opportunity. In that case, life is too short. Go start your own company.
I think the situation if fascinating and wish you'd left some way to contact you. You should definitely put together a strategy for any of the roles, VPE, CTO, or former-employee, and get some good advice.
A VP Eng is responsible for providing a human API to engineering the CEO can understand. Its all about creating predicability out of uncertainty, and if the CEO doesn't feel predicability coming out of engineering, that puts his job on the line.
Some CEO's just get it, some need Gnatt charts and resource allocations on slides, some just need to to speak with confidence and act like an alpha male, etc. In short, if you can figure out how he communicates, then you're likely to get along. If not, it's unlikely you're going to make a great API/interface - and that's ok. Better to let someone else take on the role than to be frustrated.
Although I hate to advocate this, having a CTO role is a nice way to vest for another 6-12months, relax a bit and start looking for new opportunities.
Help them find a good VP, if you like the person then maybe they can help run interference with the CEO and let you focus on the things you like. If you don't like the new VP, then it's really time to move on to a new company.
However... if the original poster feels up to it, he might decide for fight rather than flight.
I'm not a confrontational guy, but I like to get my point across when I think it matters.
Assuming the original poster has a significant share of the company, even if he retires it is very worthwhile (for the good of the company) to convince the CEO of a few points that are essential to the well-being of the company:
1) Recognising technical talent is very hard. This CEO is no doubt able to recognise management talent (or lack thereof) but that doesn't mean he will be able to pick a VP of Engineering who actually has technical ability.
The VPofE position needs strong technical ability to be able to interface effectively with the dev team (no developer will have any respect for a technically weak VPofE and they'll play him like a fiddle), and so he should be recruited by both the CEO and CTO together.
2) If the original poster doesn't enjoy the whole politics game, he should be happy to step aside out of the political line of fire. However, the VPofE (particularly as a new hire) still needs to be held accountable to someone technically qualified. The CEO ain't it. Management meetings involving the CEO and VPofE should involve both the CEO and the CTO, with the CTO there to ensure that the VPofE is not exploiting the technical inability of the CEO.
3) There's nothing especially wrong with the CTO stepping out of day to day development. However, that's a different job than being part of the dev team. So what should the CTO do? Well, there's plenty to do, I presume, in terms of driving the strategic direction of the company and ensuring the technology part of the company functions well with the non-technology part (which apparently is not the case at the moment). I think it would be a very effective shift for the poster to start focusing on "the real problem": "the front office's lack of vision and an inability to communicate clearly whatever vision they might have". That can largely be done by walking around and talking to people.
Freed from operational and dev duties, I think one of the CTO's primary respponsibility becomes to close that gap - and then any other "high-level" gaps that exist.
In short:
* Let the VPofE deal with development and managing the dev team.
* Hold him accountable in joint meetings with the CEO
* Focus on fixing the larger problems between the company's tech and non-tech silos
Of course, this requires building a stronger relationship with the CEO. However, this need not be such a tall task once the development responsibilities are delegated away, since those appear to be a big point of friction. Also, I imagine the CEO will respect this kind of reaction (much more than "Really? Then I quit! cries", anyway).
I would guess based on your comments and the fact that you're asking this question that politics are not your strong suit. "Politics", b.t.w., is just the natural state of people working together... it can be dysfunctional or functional, but as soon as you have 3 people, you have some kind of politics.
Since politics are a major component of management, you may actually be happier not doing management.
In situations like this the CEO is probably overestimating his ability to find a Magical VP Technology that will magically solve all his problems (unless he has someone in mind, a buddy from a previous company, for example). Likely he will spend 6-9 months trying to find someone, finally hire someone imperfect in despair, and spend the next year or two discovering that person is incompetent, too. But now I'm really just projecting.
If you don't like the CEO it may be time to move on. Life is to short to work with people you don't enjoy spending time with.