Let's say that I am a human living in the Star Trek universe, during the time that any Starship Enterprise exists. I want to send Captain Kirk a letter. How would I address it so that it ought get to him?
Given that the location of the USS Enterprise seems to be at least slightly classified (and when they're on fleet maneuvers, very classified), you'd probably need to send your letter in electronic form to Starfleet Headquarters to be forwarded onward the next time the ship makes contact and downloads a message bundle. We see several examples of this in the various Trek shows.
ARCHER: What's the word from home?
TUCKER: The usual, engineering updates. Oh, and Duvall got promoted. They're giving him the Shenandoah.
ARCHER: Duvall got his own command? Thank God we're a hundred light years away.
TUCKER: And I got a letter from Natalie.
COMM VOICE: Bridge to Captain Picard.
PICARD: Picard here.
COMM VOICE: There's a personal message for you from Earth.
In the instances where someone aboard the Enterprise sent a message to someone else, they did not seem to use anything like an email address. Rather they would simply say to the computer "Prepare a message for Admiral Nechayev at Star Fleet Command" From that, I believe it can be construed that the computer is expected to locate the correct person, or to notify the sender if the recipient cannot be identified. The most likely mechanism would be for the computer to work backwards, starting with "Star Fleet Command" and then either interrogating a database at command to locate Admiral Nechayev, or simply sending the message to command and expecting that further routing would be handled behind the scenes, so to speak. The underlying mechanisms might not be all that different than what we use now, simply made more user friendly and intelligent.
There is a full (albeit high level to account for the fiction - subspace etc) breakdown of every part of the in-universe methods and operations of communication between two parties at any range. Covered includes intra-ship comms, the personal communicator, ship to ground, ship to ship, non-starfleet contacts, the subspace communications network in (fictional) detail and of course - the universal translator. Check it out, it's a good read. However, at "more pages than i care to violate copyright laws about" of mostly diagrams and their explanations, a condensed version follows.
To cover the letter writing part: The sender speaks or taps into a device (not just comm badge apparently), message is encrypted to starfleet standards / U.T. analysis, this will usually require an id header eg "Ensign Redshirt to the bridge" or "Computer, open a channel to Ambassador Chooch on Terra Prime". Communications are routed through successive subspace relays to the recipient once the relevant network has id'ed the persons in question from previous face-to-face encounters stored in the system or analysis of intended recipient/location data. Concerning to "5 year mission" aspect: Starships regularly drop temporary subspace relays out the back while travelling to strengthen subspace signal quality in previously unknown areas of the galaxy.
References: Section 8 of the Star Trek The Next Generation Technical Manual ISBN 1-85283-340-8
Starfleet was designed to be similar to our various military organizations over the years, specifically the naval ones. So I would assume that the process is similar to how one currently sends an email to a recipient who is actively deployed. There is a delay and it arrives after passing the proper clearance channels/firewalls/whatever security Starfleet deems necessary.
So you would address a letter to Captain Kirk the same way that you would address one to the captain of one of the Navy's current vessels, whatever that process may be.