As long as you're using Windows Live Messenger (with or without Plus!), you just need to open a chat window with the contact that's offline.
The messages you type will be sent to them, but they must also be using a Messenger which supports offline Messaging. Messenger 7.5 (Possibly a few earlier versions also) can receive offline messages, but can’t send them. (This was the case in 7.5 for me, anyway)