People who use Skype store important information in Skype chat history, that is true, unfortunatly. How often you realise that important url,contact,login info, etc left on your work computer or even was formatted with last OS reinstall ?  There is a perfect solution to overcome this:

and this solution is...Store important information outside Skype :) But, thats not what I am talking about.

Some of Skype call recording software support brilliant feature to store call recording and chat session in GMail account! Thus make it possible to search through them using powerful Gmail search.

The winner is:

G-recorder

14-day trial for free, $25 for personal and $40 for corporate. Supports GMail and Google Apps. Upload chats and call records. http://www.g-recorder.com/usage.htm for more info.

Other related software

Piston. Saves chat messages too, never tried. $25. Visit http://www.pistonsoft.com/skype-recorder.html

Free call recording. Never tried, but seems to be free.Visit http://voipcallrecording.com/

Linux skype call recorder. Seems to work. Visit: http://atdot.ch/scr/download/