Como você instalou o openjdk6, faça o seguinte:
- Faça download do Outlook Messenger no site.
- Vá para a pasta de download, clique com o botão direito do mouse em "outlookmessenger7.jar" e selecione "Extrair aqui".
- Ir para a nova pasta "OM".
- Clique com o botão direito do mouse em "OutlookMessenger.jar", selecione Propriedades.
- Vá para a guia "Permissões" e marque "Permitir a execução do arquivo como programa". Feche essa janela.
- Clique com o botão direito do mouse em "OutlookMessenger.jar", selecione "Abrir com o OpenJDK Java 6 Runtime".
Lá vai você! (Não há necessidade de instalação e não há necessidade do terminal.)