>I think it's probably best to think of it as something like a naval
>deployment. It's not so much that they spent 5 years "at sea", but it
>was 5 years without a lengthy time in drydock. At best, they stopped
>at the occasional starbase for supplies and fuel, but nothing major.

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.