GCM
Personally, I would go for GCM (Galois Counter Mode) since it is efficient – meaning: it handles pretty much everything you’ld expect from it, while other modes sometimes tend to lack a specific feature here and there (see image below for a comparison that shows what I’m hinting at). Also, GCM has a pretty good performance (assuming non-flawed implementation). As you most probably already know, it provides Galois mode of authentication with the well-known CTR mode encryption. The CTR aspect practically means that it doesn’t need any padding (which avoids related attack potential) and it means that you keep a bit of flexibility when it comes to message/package lengths (something CCM for example doesn’t offer, since it uses a fixed block length). Also, the Galois field multiplication used for authentication can be computed in parallel, which enables higher speed/throughput than those authentication algorithms that use chaining modes (like CBC etc). Btw: in case you decide to check on GCM, you might find it handy to know that NIST Special Publication 800-38D includes recommendations for IV selection etc.
The rest…
An alternative at the top of my list would have been EAX mode, which also provides several desirable attributes. But: EAX is a “two-pass scheme”… making it slower than well designed one-pass schemes that are based on the same primitives. Since your designing a messaging/storage protocol, you probably will want to get your hands on all the speed you can get. Two-pass seems not to be an option in that case, pushing EAX down on the list.
Now, you also mentioned CCM. That mode is only defined for block ciphers with a block length of 128 bits, which might be a bit restrictive in size for messaging et al. Which is why I would like to remind you of GCM’s counter mode again…
Last on the list of things you’ve mentioned is OCB. I’m a bit uncomfortable when thinking about OCB, because Ferguson found collision attacks on OCB. The attack limits the data that can safely be encrypted with OCB to around and about 64GB per key. That’s about the same 64 GB limit that GCM has (GCM limits plaintext size to $2^{39} − 256$ bits for any given key and IV combination), but we have to remember that GCM’s limit is “by design”… in the case of OCB, it’s “the result of a collision attack”. From a security perspective, I would therefore tend to avoid OCB. We all know attacks can only get better.
There are a few other things that might or might not make a bit of sense, depending on the individual setting… but in the end, I personally would advise to use GCM for a messaging and storage protocol.
Comparing some of the options…
To compare, you might also want to check out the nice comparison table on slide 7 of this PPT file by David Wagner. I’ll quote it as a graphic here for reading convenience (as you’ll notice GCM is a winner):

EDIT
Sometimes, my brain seems to be a bit slow when it comes to remembering papers I’ve once been reading.
Anyway, I’m pretty confident you’ll enjoy reading “Basic comparison of Modes for Authenticated-Encryption (IAPM, XCBC, OCB, CCM, EAX, CWC, GCM, PCFB, CS)” (PDF) which compares a truckload of modes in terms of attributes, speed, implementation, memory usage, tables showing things like the number of the underlying block cipher invocations for each mode, etc.
After reading that, you’ll have ample info at hand to decide for yourself what makes most sense.