Sometime in either late July or early August 2006, AOL accidentally released a sample of approximately 20 million queries performed by roughly 658 thousand AOL users, which spanned a 3 month period from March to May of that year. I have condensed the majority of this data down to a usable format in the Keyword Suggestion Tool.
Based upon market share info reported for the major search engines in November 2005 and the percentage of AOL searches that the data represents (according to a comment made by AOL spokesman Andrew Weinstein), this tool will give you a rough estimate for how much traffic each of the 3 major search engines (Google, Yahoo! and MSN) could have received for a given keyphrase over a one month period within that time frame.
Clicking on the number under the Google column opens up Google Trends for that phrase for the month of May.