I've heard some speculation about this -- basically, the general consensus among people I've discussed it with is that the Federation laid claim to a fairly large region of space that was partially to mostly unexplored or unknown, at least to any of the races/empires/nations they were in contact with at the time (such as the Klingons). Their initial exploration efforts set up a lot of nodal supply posts, border stations like K-7, etc, but a lot of that space was still pretty much unknown - kind of like the space between cities in the rural midwest, but more so. The Connies' 5-year missions were to go out and poke about in that space, rather than going /out/ beyond the current boundaries, for the most part.