Have you tried trillian? I've been using it for around 10 years or so. They have a client for Windows, OSX and I've tried it before on WINE as well. They also have a mobile client on nearly every platform. They recently added chat sync to their client so that you can see your missed messages when you log in from another device.
Example:
Someone left you 10 messages on your home computer while you were afk.
You log in from your phone and as soon as you do, your missed conversations pop up as well as any chat windows + messages you had open on your computer before leaving. It also has an option to push your messages to email on the mobile clients when you're offline and I believe there is a way to do it for the desktop client as well (just not as obvious).
---
I also think it generally stores your messages by default until you log back in (if you're offline on all devices) as well. I generally get a storm of chat popups if I have been offline for a day or two on all devices as soon as I log onto trillian again. I don't think I would always trust it to work, but it generally seems be fine for most protocols.
It supports most protocols (xmpp/jabber, msn chat, google chat, aim, icq, yahoo, facebook chat, twitter, irc and some others).
The only annoyance of trillian is the free version has some ads for their products (a recent decision by them to reevaluate what their call their "pro" version). They went from making their free version lack a few features to having everything except their cloud chat history sync backup and making their "pro" version a subscription instead of a one time payment. I regret that they went the subscription route and ads showing up occasionally in the chat window, but I still find it's better than other clients. It's 12 dollars a year though to buy the pro version.
It does have built in encryption for chatting, but it's sadly not OTR (http://www.cypherpunks.ca/otr/) and only works with users on trillian. There is an unofficial OTR plugin out for trillian, but it's always been sort of buggy and I don't think it has been supported by the developer for a while. There is a fork of the original, no longer supported trillian OTR plugin out (http://sourceforge.net/projects/trillianotr) so it might be working better now. I'll have to give it a try.