I recently discovered that my Yahoo Premium account woudn't do a search more than 30 days ago.
I did some searching on the internet and discovered a product called Yahoo Zimbra. It looks like Outlook Express. Anyway, after I downloaded it and installed it I was able to research my mail all the way to the beginning.
It took several hours to download all 25,000 of my emails so it was best done while I was sleeping but it was worth it.
It also works with GMail and AOL
http://www.zimbra.com/products/desktop.html