Howzabout this: the ships are Starfleet registered, but the operating authority is delegated to the major Federation members, specifically, those who have their own sufficiently large space program. The Enterprise operates under the United Earth Space Probe Agency, the Intrepid operated under some office of Vulcan Space Central or the Vulcan Science Academy.
And that might be a way to work in a variation of the "Spock is the first Vulcan in Starfleet" idea. The notion of Vulcan operating a separate Starfleet Academy facility isn't such a bad idea, and fits quite well with the typical Vulcan attitude of staying apart from all those pesky emotional humans, with the graduates being directed mainly to either ground assignments or ships under Vulcan control, like the Intrepid.
Spock, however, could very well have been the first Vulcan to attend Starfleet Academy on Earth, thus opening up a much wider career field and, essentially, telling Vulcan, and his father, to bite his pointy-eared ass.